可能是最简单的Dijkstra写法 基于python
adj = {1: {2: 1, 3: 12}, 2: {4: 3, 3: 9}, 3: {5: 5}, 4: {3: 4, 5: 13, 6: 15}, 5: {6: 4}}
dis = {2: 1, 3: 12, 4: 666, 5: 666, 6: 666}
parents_node = {2: 1}
visited = []
min_p = None
min_d = None
for i in range(len(dis)):
sorted_dis = sorted(dis.items(), key=lambda x:x[1]) # .items()让字典元素变成元组
# 找到一个未访问过的最近点
for p, d in dis.items():
if p not in visited:
min_p = p
min_d = d
visited.append(p)
break
if min_p not in adj: continue # p 找不到可以达到的点
# 经过中转站到达的距离比直接到达快 需要更新
# s p e s是起点 p是未访问的最小点(中转站) e是从p可到达的点
for e, d in adj[min_p].items():
dis[e] = min(dis[e], min_d + d)
print(dis)
# {2: 1, 3: 8, 4: 4, 5: 15, 6: 19}
参考
网友评论