Floyd最短路径算法代码

Floyd-Warshall算法是一种用于计算所有节点对之间最短路径的经典图算法。它适用于加权有向或无向图，即使图中存在负权重边。以下是使用Python编写的Floyd-Warshall算法的简单版本：

def floyd_warshall(graph):
    n = len(graph) # 获取节点数
    dist = graph.copy() # 复制原图作为距离矩阵
    for k in range(n): # 对每个中间节点进行遍历
        for i in range(n):
            for j in range(n):
                # 如果通过中间节点k的路径比直接相连更短，则更新路径
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 示例图（邻接矩阵表示）
graph = [
    [0, 4, 0, 0],
    [4, 0, 8, 0],
    [0, 8, 0, 11],
    [0, 0, 11, 0]
]

floyd_warshall_result = floyd_warshall(graph)
print("最小路径矩阵: ")
for row in floyd_warshall_result:
    print(row)