- Floyd算法是解决多源最短路径的算法，优点是简单易于理解。
主要流程如下：
- 1 初始化矩阵初始值
- 2 遍历每一个节点为中介点，对于所有节点组合，计算经中介点是否更近，更近则保存结果
- 3 循环结束
-
如下例
幻灯片1.jpg
幻灯片2.jpg
幻灯片3.jpg
幻灯片4.jpg
幻灯片5.jpg
幻灯片6.jpg
幻灯片7.jpg
- 代码如下
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)
