弗洛伊德法

发表于 更新于 分类于 ，

弗洛伊德（Floyd）算法是解决任意两点间的最短路径的一种算法，适用有向图（含负权值）但不可用于存在负权环路的图（因为每过一次负权值环路路劲长度就会减小）。此算法时间复杂度为\(O(n^3)\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 初始距离
d = [[0, 2, 6, 4],
     [float('inf'), 0, 3, float('inf')],
     [7, float('inf'), 0, 1],
     [5, float('inf'), 12, 0]]

for k in range(4):
    for i in range(4):
        for j in range(4):
            d[i][j] = min(d[i][k]+d[k][j],d[i][j])

# 最短距离
for i in d:
    print(i)

注意：对中间节点k的遍历应当保证在最外层循环，以正确更新每个点间的最小距离。