1 def Dijkstra(network,s,d): # 迪杰斯特拉算法算s-d的最短路径，并返回该路径和代价 2 print ( " Start Dijstra Path…… " ) 3 path=[] # s-d的最短路径 4 n=len(network) # 邻接矩阵维度，即节点个数 5 fmax=9
1 def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径，并返回该路径和代价 2 print("Start Dijstra Path……") 3 path=[]#s-d的最短路径 4 n=len(network)#邻接矩阵维度，即节点个数 5 fmax=999 6 w=[[0 for i in range(n)]for j in range(n)]#邻接矩阵转化成维度矩阵，即0→max 7 book=[0 for i in range(n)]#是否已经是最小的标记列表 8 dis=[fmax for i in range(n)]#s到其他节点的最小距离 9 book[s-1]=1#节点编号从1开始，列表序号从0开始 10 midpath=[-1 for i in range(n)]#上一跳列表 11 for i in range(n): 12 for j in range(n): 13 if network[i][j]!=0: 14 w[i][j]=network[i][j]#0→max 15 else: 16 w[i][j]=fmax 17 if i==s-1 and network[i][j]!=0:#直连的节点最小距离就是network[i][j] 18 dis[j]=network[i][j] 19 for i in range(n-1):#n-1次遍历，除了s节点 20 min=fmax 21 for j in range(n): 22 if book[j]==0 and dis[j]<min:#如果未遍历且距离最小 23 min=dis[j] 24 u=j 25 book[u]=1 26 for v in range(n):#u直连的节点遍历一遍 27 if dis[v]>dis[u]+w[u][v]: 28 dis[v]=dis[u]+w[u][v] 29 midpath[v]=u+1#上一跳更新 30 j=d-1#j是序号 31 path.append(d)#因为存储的是上一跳，所以先加入目的节点d，最后倒置 32 while(midpath[j]!=-1): 33 path.append(midpath[j]) 34 j=midpath[j]-1 35 path.append(s) 36 path.reverse()#倒置列表 37 print(path) 38 #print(midpath) 39 print(dis) 40 #return path 41 42 network=[[0,1,0,2,0,0], 43 [1,0,2,4,3,0], 44 [0,2,0,0,1,4], 45 [2,4,0,0,6,0], 46 [0,3,1,6,0,2], 47 [0,0,4,0,2,0]] 48 Dijkstra(network,1,6)