floyd算法求最短路径

Floyd算法是一种用于解决带权有向图最短路径问题的算法，可以求出图中任意两点之间的最短路径。以下是Floyd算法的步骤：

1. 初始化：将每个顶点之间的距离设置为正无穷，如果两个顶点之间有边，则将它们之间的距离设置为边的权值。
2. 对于每一个中间顶点k，遍历所有的顶点i和j，如果从i到j的路径经过k比直接从i到j的路径更短，则更新i到j的最短路径为i到k再到j的路径。即，如果dist[i][j] > dist[i][k] + dist[k][j]，则更新dist[i][j] = dist[i][k] + dist[k][j]。
3. 重复步骤2，对于所有的中间顶点k，直到没有更新操作。

最终，dist[i][j]表示从顶点i到顶点j的最短路径。

以下是Floyd算法的Python代码实现：

def floyd(graph):
    n = len(graph)
    dist = [[float('inf') for _ in range(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] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

其中，graph是邻接矩阵表示的带权有向图，n是顶点数。