Python如何实现并输出迪杰斯特拉算法的最短路径结果？
- 内容介绍
- 文章标签
- 相关推荐
本文共计617个文字，预计阅读时间需要3分钟。
pythondef dijkstra(network, start, destination): # 初始化距离表和前驱节点表 distances={node: float('infinity') for node in network} distances[start]=0 predecessors={node: None for node in network}
# 创建一个空集合来存储已访问的节点 visited=set()
# 当还有未访问的节点时，进行循环 while len(visited) # 将当前节点标记为已访问 visited.add(current_node) # 更新相邻节点的距离 for neighbor, weight in network[current_node].items(): if neighbor not in visited: new_distance=distances[current_node] + weight if new_distance # 返回起点到终点的最短路径 path=[] current_node=destination while current_node is not None: path.append(current_node) current_node=predecessors[current_node] path.reverse() return path 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)
本文共计617个文字，预计阅读时间需要3分钟。
pythondef dijkstra(network, start, destination): # 初始化距离表和前驱节点表 distances={node: float('infinity') for node in network} distances[start]=0 predecessors={node: None for node in network}
# 创建一个空集合来存储已访问的节点 visited=set()
# 当还有未访问的节点时，进行循环 while len(visited) # 将当前节点标记为已访问 visited.add(current_node) # 更新相邻节点的距离 for neighbor, weight in network[current_node].items(): if neighbor not in visited: new_distance=distances[current_node] + weight if new_distance # 返回起点到终点的最短路径 path=[] current_node=destination while current_node is not None: path.append(current_node) current_node=predecessors[current_node] path.reverse() return path 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)