参考：坐在马桶上看算法：只有五行的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]
