Floyd算法-求最短路径

理解

代码

# -*- coding: utf-8 -*-
"""
Created on Fri May  6 13:54:10 2022

Floyd算法
    用途:计算任意两点之间的最短路径
    复杂度:时间复杂度O(n^3)
    算法核心:
        直接相连D[i][j],加入K节点后间接相连D[i][k]+D[k][i]
        比较这种相连方式,哪种路径更短,将其作为两者的最短路径
"""
import numpy as np
def Floyd(D,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if(D[i][j]>D[i][k]+D[k][j]):
                    D[i][j]=D[i][k]+D[k][j]
        print("第{}次".format(k+1))
        print(D)

D=np.array([[0,2,np.inf,1,8],
            [6,0,3,2,np.inf],
            [np.inf,np.inf,0,4,np.inf],
            [np.inf,np.inf,2,0,3],
            [3,np.inf,np.inf,np.inf,0]])        
Floyd(D,5)

结果

第1次
[[ 0.  2. inf  1.  8.]
 [ 6.  0.  3.  2. 14.]
 [inf inf  0.  4. inf]
 [inf inf  2.  0.  3.]
 [ 3.  5. inf  4.  0.]]
第2次
[[ 0.  2.  5.  1.  8.]
 [ 6.  0.  3.  2. 14.]
 [inf inf  0.  4. inf]
 [inf inf  2.  0.  3.]
 [ 3.  5.  8.  4.  0.]]
第3次
[[ 0.  2.  5.  1.  8.]
 [ 6.  0.  3.  2. 14.]
 [inf inf  0.  4. inf]
 [inf inf  2.  0.  3.]
 [ 3.  5.  8.  4.  0.]]
第4次
[[ 0.  2.  3.  1.  4.]
 [ 6.  0.  3.  2.  5.]
 [inf inf  0.  4.  7.]
 [inf inf  2.  0.  3.]
 [ 3.  5.  6.  4.  0.]]
第5次
[[ 0.  2.  3.  1.  4.]
 [ 6.  0.  3.  2.  5.]
 [10. 12.  0.  4.  7.]
 [ 6.  8.  2.  0.  3.]
 [ 3.  5.  6.  4.  0.]]