flody最短路径 python

Floyd算法是一种多源最短路径算法，可以求出图中任意两点之间的最短路径。下面是Python实现。

假设我们有一个 n × n 的邻接矩阵 graph 表示图，其中 graph[i][j] 表示从节点 i 到节点 j 的边权重，如果 i 和 j 之间没有边相连，则将 graph[i][j] 设置为无穷大。

def floyd(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            dist[i][j] = graph[i][j]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

其中，dist[i][j] 表示从节点 i 到节点 j 的最短路径长度，初始时，将其设置为邻接矩阵中的边权重。接下来，对于每个中间节点 k，我们尝试通过 k 来更新 i 和 j 之间的最短路径长度。如果从 i 到 k 和从 k 到 j 的路径长度之和小于当前的最短路径长度，那么更新最短路径长度。

最后，返回 dist 即可。