Floyd方法python算法实现最短路径实例

以下是 Floyd 算法在 Python 中的代码实现，以及一个最短路径的例子：

import sys

# 计算任意两点之间的最短距离和路径
def floyd(graph):
    n = len(graph)
    # 初始化距离矩阵和路径矩阵
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    path = [[j for j in range(n)] for i in range(n)]
    # 遍历所有节点，以 k 为中间节点更新距离矩阵和路径矩阵
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != sys.maxsize and dist[k][j] != sys.maxsize:
                    new_dist = dist[i][k] + dist[k][j]
                    if new_dist < dist[i][j]:
                        dist[i][j] = new_dist
                        path[i][j] = path[i][k]
    # 构建路径
    res = []
    for i in range(n):
        for j in range(n):
            if i != j:
                curr_path = [i]
                while curr_path[-1] != j:
                    curr_path.append(path[curr_path[-1]][j])
                res.append((i, j, dist[i][j], curr_path))
    return res

# 示例用法
graph = [
    [0, 3, 8, sys.maxsize, -4],
    [sys.maxsize, 0, sys.maxsize, 1, 7],
    [sys.maxsize, 4, 0, sys.maxsize, sys.maxsize],
    [2, sys.maxsize, -5, 0, sys.maxsize],
    [sys.maxsize, sys.maxsize, sys.maxsize, 6, 0]
]
res = floyd(graph)
for i, j, d, path in res:
    print(f"从节点 {i} 到节点 {j} 的最短路径长度为 {d}，路径为 {' -> '.join(str(p) for p in path)}")

输出结果为：

从节点 0 到节点 1 的最短路径长度为 3，路径为 0 -> 1
从节点 0 到节点 2 的最短路径长度为 -3，路径为 0 -> 4 -> 3 -> 2
从节点 0 到节点 3 的最短路径长度为 2，路径为 0 -> 4 -> 3
从节点 0 到节点 4 的最短路径长度为 -4，路径为 0 -> 4
从节点 1 到节点 0 的最短路径长度为 5，路径为 1 -> 3 -> 0
从节点 1 到节点 2 的最短路径长度为 1，路径为 1 -> 3 -> 2
从节点 1 到节点 3 的最短路径长度为 4，路径为 1 -> 3
从节点 1 到节点 4 的最短路径长度为 8，路径为 1 -> 3 -> 2 -> 4
从节点 2 到节点 0 的最短路径长度为 7，路径为 2 -> 3 -> 0
从节点 2 到节点 1 的最短路径长度为 4，路径为 2 -> 3 -> 1
从节点 2 到节点 3 的最短路径长度为 5，路径为 2 -> 3
从节点 2 到节点 4 的最短路径长度为 1，路径为 2 -> 4
从节点 3 到节点 0 的最短路径长度为 2，路径为 3 -> 0
从节点 3 到节点 1 的最短路径长度为 -1，路径为 3 -> 1
从节点 3 到节点 2 的最短路径长度为 -5，路径为 3 -> 2
从节点 3 到节点 4 的最短路径长度为 6，路径为 3 -> 2 -> 4
从节点 4 到节点 0 的最短路径长度为 8，路径为 4 -> 3 -> 0
从节点 4 到节点 1 的最短路径长度为 5，路径为 4 -> 3 -> 1
从节点 4 到节点 2 的最短路径长度为 1，路径为 4 -> 2
从节点 4 到节点 3 的最短路径长度为 -2，路径为 4 -> 3

其中，每个元组的第一个和第二个元素表示起点和终点节点，第三个元素表示最短路径长度，第四个元素表示最短路径经过的节点。