多源最短路径 Floyd算法

1. Floyd算法是解决多源最短路径的算法，优点是简单易于理解。
   主要流程如下：

• 1 初始化矩阵初始值
• 2 遍历每一个节点为中介点，对于所有节点组合，计算经中介点是否更近，更近则保存结果
• 3 循环结束

2. 如下例

   
   幻灯片1.jpg

幻灯片2.jpg 幻灯片3.jpg 幻灯片4.jpg 幻灯片5.jpg 幻灯片6.jpg 幻灯片7.jpg

3. 代码如下

from copy import copy

Inf = float('inf')

def load_graph():
    N=6
    graph = [[0, 1, 12, Inf, Inf, Inf],
             [1, 0, 9, 3, Inf, Inf],
             [12, 9, 0, 4, 5, Inf],
             [Inf, 3, 4, 0, 13, 15],
             [Inf, Inf, 5, 13, 0, 4],
             [Inf, Inf, Inf, 15, 4, 0]]

    return graph,N

if __name__ == '__main__':

    graph,N = load_graph()

    #distance matrix
    distance = copy(graph)

    # floyd
    for k in range(N):
    #k为中介点
        for i in range(N):
            for j in range(N):
                if i==j or i==k or j==k: continue
                if graph[i][k]+graph[k][j]<distance[i][j]:
                    distance[i][j] = graph[i][k]+graph[k][j]
                    distance[j][i] = distance[i][j]

    print(distance)

4.优缺点

• 1 优点
  • 算法简单，易于理解
  • 对于稠密图更高效
• 2 缺点
  • 复杂度较高 O(n3)