【算法-图】最短路径Floyd算法

参考：坐在马桶上看算法：只有五行的Floyd最短路算法
http://developer.51cto.com/art/201403/433874.htm

问题描述：

求解各个站点两两之间的最短距离

路径图

关键代码：

for k in range(length):                          #可以经过k点
    for i in range(length):                      #[i,j]点遍历
        for j in range(length):
            if D[i,j] > (D[i,k]+D[k,j]):
                D[i,j] = D[i,k]+D[k,j]            #两个顶点直接较小的间接路径替换较大的直接路径
                path[i,j]=k                       #记录前驱路径

思路：

• 最外层循环k表示可以经过【0,1,2...k】点时，修正一下最短路
• 中间循环i,j表示点集两两之间若经过k点是否能更短
• 如果更短，则更新两点最短距离，记录k点。

理解：
可以理解为，允许经过0~k点的情况下的最短距离；
在现有路径下，从i点到j点，走从k点周转一下更近；
而i到k、k到j可能不是直达；
搜寻i→j路线时，先找到【i,j】之间的k，再找【i,k】【k,j】的路线，以此类推

完整例子

import numpy as np
D=np.array([0,2,6,4,np.inf,0,3,np.inf,7,np.inf,0,1,5,np.inf,12,0]).reshape([4,4])
print('InitialDis:\n',D)

length=D.shape[0]                                 #一共有多少个点
path=np.zeros((length,length))-1
for k in range(length):                          #可以经过k点
    for i in range(length):                      #[i,j]点遍历
        for j in range(length):
            if D[i,j] > (D[i,k]+D[k,j]):
                D[i,j] = D[i,k]+D[k,j]            #两个顶点直接较小的间接路径替换较大的直接路径
                path[i,j]=k                      #记录前驱路径
                
                
print('Distance:\n',D)
print('PathSearch:\n',path)

InitialDis:
 [[  0.   2.   6.   4.]
 [ inf   0.   3.  inf]
 [  7.  inf   0.   1.]
 [  5.  inf  12.   0.]]
Distance:
 [[  0.   2.   5.   4.]
 [  9.   0.   3.   4.]
 [  6.   8.   0.   1.]
 [  5.   7.  10.   0.]]
PathSearch:
 [[-1. -1.  1. -1.]
 [ 3. -1. -1.  2.]
 [ 3.  3. -1. -1.]
 [-1.  0.  1. -1.]]

以2→1为例，直观上看路径为2→3→4→1，长度为3+1+5=9
在Distance矩阵中，D[1,0]=9
在Path矩阵中，D[1,0]=3→D[1,3]=2/D[3,0]=-1→D[1,2]=-1，∴1→2→3→0

#根据距离矩阵获取路径
def getPath(i,j,path,out):         #只想打印路径的话不用out，这里out为传址调用
    if i==j:
        return
    elif path[i,j]==-1:
        out.append(j)
        print(j)
    else:
        getPath(i,int(path[i,j]),path,out)
        getPath(int(path[i,j]),j,path,out)

out=[1]
getPath(1,0,path,out)
print(out)

2
3
0
[1, 2, 3, 0]