法）
使⽤Floyd-Warshall算法 求图两点之间的最短路径不允许有负权边，时间复杂度⾼，思路简单
1 # 城市地图（字典的字典）
2 # 字典的第1个键为起点城市，第2个键为⽬标城市其键值为两个城市间的直接距离 3 # 将不相连点设为INF,⽅便更新两点之间的最⼩值 4 INF = 99999
5 G = {1:{1:0, 2:2, 3:6, 4:4}, 6 2:{1:INF, 2:0, 3:3, 4:INF}, 7 3:{1:7, 2:INF, 3:0, 4:1}, 8 4:{1:5, 2:INF, 3:12, 4:0} 9 }10
11 # 算法思想：
12 # 每个顶点都有可能使得两个顶点之间的距离变短
13 # 当两点之间不允许有第三个点时，这些城市之间的最短路径就是初始路径14
15 # Floyd-Warshall算法核⼼语句
16 # 分别在只允许经过某个点k的情况下，更新点和点之间的最短路径
17 for k in G.keys(): # 不断试图往两点i,j之间添加新的点k，更新最短距离18 for i in G.keys():
19 for j in G[i].keys():
20 if G[i][j] > G[i][k] + G[k][j]:21 G[i][j] = G[i][k] + G[k][j]22 23
24 for i in G.keys():25 print G[i].values()
结果：
[0, 2, 5, 4][9, 0, 3, 4][6, 8, 0, 1][5, 7, 10, 0]
因篇幅问题不能全部显示，请点此查看更多更全内容