python中用佛洛依德算法求解最小路径问题

在Python中，弗洛伊德(Floyd-Warshall)算法常用于解决图中的最短路径问题，包括寻找所有顶点对之间的最短路径。这个动态规划算法适用于有向或无向、加权或非加权的图，特别是当存在负权重边时，其他简单算法如Dijkstra可能无法直接应用。

以下是使用Python实现弗洛伊德算法的基本步骤：

1. 初始化一个二维数组`dist`，其中`dist[i][j]`表示从节点i到节点j的最短路径。如果不存在边，则初始化为无穷大（通常用`float('inf')`或很大的数字）。

2. 对于每一对节点(i, j)，通过所有中间节点k计算出一条可能更短的路径：`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`。

3. 重复此过程直到所有的最短路径都更新完毕。每次迭代都会尝试找到一个新的最短路径，所以最终的`dist`矩阵将包含整个图中最短路径的信息。

def floyd_warshall(graph):
    n = len(graph)
    dist = [[graph[i][j] if i != j else 0 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是一个邻接矩阵表示的图
graph = [[0, 4, float('inf'), 2],
         [4, 0, 8, 6],
         [float('inf'), 8, 0, 7],
         [2, 6, 7, 0]]

shortest_paths = floyd_warshall(graph)