floyd算法求最短路径例子

假设有下面这个图，我们要求出从A到其他各个节点的最短路径：

     2       3
A ------ B ------ C
|  1           4   |
|      5           |
D ---------------- E
          6

首先我们初始化一个二维数组`dist`，表示起点A到各个节点的最短距离。将起点A到自己的距离设为0，其他节点的距离先设为无穷大（因为我们还不知道最短距离是多少）：

dist = [
    [0, inf, inf, inf, inf],
    [inf, 0, inf, inf, inf],
    [inf, inf, 0, inf, inf],
    [inf, inf, inf, 0, inf],
    [inf, inf, inf, inf, 0]
]

接下来，我们需要利用Floyd算法，逐步更新`dist`数组，直到找到所有节点的最短路径。

Floyd算法的核心是三重循环，其中最外层的循环控制“中转节点”，即在更新A到B的最短距离时，需要通过一个中转节点（可能是C、D、E中的任意一个）来实现。中间的两重循环分别遍历所有的起点和终点，如果发现通过当前中转节点可以得到更短的路径，则更新`dist`数组。

下面是Floyd算法的Python实现：

def floyd(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

dist = [
    [0, 2, 1, inf, inf],
    [inf, 0, inf, inf, inf],
    [inf, 3, 0, 4, inf],
    [inf, inf, inf, 0, 6],
    [inf, inf, inf, inf, 0]
]

floyd(dist)

print(dist)

输出结果为：

[
    [0, 2, 1, 5, 11],
    [inf, 0, inf, inf, inf],
    [inf, 3, 0, 4, 10],
    [inf, inf, inf, 0, 6],
    [inf, inf, inf, inf, 0]
]

可以看到，最终`dist`数组中包含了A到各个节点的最短距离。比如，A到节点B的最短距离为2，A到节点C的最短距离为1，A到节点D的最短距离为5，A到节点E的最短距离为11。