floyd求最短路径python

Floyd-Warshall算法是一种用于计算有向图或无向图中最短路径的经典动态规划方法。在Python中，你可以通过创建一个二维数组并更新其元素来实现Floyd算法。以下是基本步骤：

1. 初始化一个二维数组`dist`，其中`dist[i][j]`表示从节点i到节点j的最短距离，默认值为无穷大（通常设置为`float('inf')`），除非直接相连，否则初始化为图中的边长。

2. 对于每个中间节点k（0到n-1，n为节点总数）遍历所有节点对(i, j)，如果`dist[i][k] + dist[k][j]`小于`dist[i][j]`，则更新`dist[i][j]`为新的更短路径。

3. 重复此过程，每次迭代都会检查是否存在通过当前未考虑的节点k的更短路径。这个过程会持续进行n(n-1)/2次迭代，直到不会有更短路径被发现。

4. 最终得到的`dist`数组中的元素就是从每个节点到其他所有节点的最短路径。

下面是一个简单的Python版本的Floyd-Warshall算法实现：

def floyd_warshall(graph):
    n = len(graph)
    dist = [[graph[i][j] if i != j else float('inf') for j in range(n)] for i in range(n)]
    
    # 检查并更新每条边
    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是一个邻接矩阵，如[[0, 5, inf], [2, 0, 3], [inf, 1, 0]]
graph = [[0, 5, float('inf')],
         [2, 0, 3],
         [float('inf'), 1, 0]]
shortest_paths = floyd_warshall(graph)