python实现floyd

Floyd算法，也称为 Floyd-Warshall 算法，是一种用于求解所有最短路径的动态规划方法，通常用于图论中的最短路径问题。在Python中实现Floyd-Warshall算法，可以处理有向或无向、加权或非加权的图，并且可以在任意维数上运行，但通常适用于二维数组表示的邻接矩阵。

以下是简单的Python实现：

def floyd_warshall(graph):
    n = len(graph) # 图的节点数
    dist = graph.copy() # 初始距离矩阵，等于原邻接矩阵

    for k in range(n): # 对于每个中间节点k
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]: # 如果通过k可以找到更短路径
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist # 返回改进后的最短路径矩阵

# 示例：邻接矩阵代表图的结构，0 表示没有边，正数值表示权重
graph = [
    [0, 4, 0, 0],
    [4, 0, 8, 0],
    [0, 8, 0, 7],
    [0, 0, 7, 0]
]

print(floyd_warshall(graph))