华电北风吹 2017年3月12日
未连接的边需要赋一个初始值，可以把矩阵所有元素值相加再加1。附加功能是计算最短路径的条数。
import sys def Floyd(Graph,ShortestPath,PathCount): NodeNum=len(Graph) lastShortestDistance=[[0 for i in range(NodeNum)] for j in range(NodeNum)] lastPathCount=[[0 for i in range(NodeNum)] for j in range(NodeNum)] currentShortestDistance=[[0 for i in range(NodeNum)] for j in range(NodeNum)] currentPathCount=[[0 for i in range(NodeNum)] for j in range(NodeNum)] for i in range(NodeNum): for j in range(NodeNum): lastShortestDistance[i][j]=Graph[i][j] if (Graph[i][j]>0) and (Graph[i][j]<10): lastPathCount[i][j]=1 else: lastPathCount[i][j]=0 currentShortestDistance[i][j]=lastShortestDistance[i][j] currentPathCount[i][j]=lastPathCount[i][j] for k in range(NodeNum): for i in range(NodeNum): if (i==k): continue for j in range(NodeNum): if (j==k): continue if(lastShortestDistance[i][j]<lastShortestDistance[i][k]+lastShortestDistance[k][j]): continue if(lastShortestDistance[i][j]==lastShortestDistance[i][k]+lastShortestDistance[k][j]): currentShortestDistance[i][j]=lastShortestDistance[i][j] currentPathCount[i][j]=lastPathCount[i][j]+lastPathCount[i][k]*lastPathCount[k][j] if(lastShortestDistance[i][j]>lastShortestDistance[i][k]+lastShortestDistance[k][j]): currentShortestDistance[i][j]=lastShortestDistance[i][k]+lastShortestDistance[k][j] currentPathCount[i][j]=lastPathCount[i][k]*lastPathCount[k][j] lastShortestDistance=currentShortestDistance lastPathCount=currentPathCount for i in range(NodeNum): for j in range(NodeNum): ShortestPath[i][j]=currentShortestDistance[i][j] PathCount[i][j]=currentPathCount[i][j] return None nodeNum=4 graph=[[0,1,1,10],[1,0,10,10],[1,10,0,1],[10,10,1,0]] shortestPath=[[0 for i in range(nodeNum)] for j in range(nodeNum)] pathCount=[[0 for i in range(nodeNum)] for j in range(nodeNum)] Floyd(graph,shortestPath,pathCount) print(shortestPath) print(pathCount)