可能是最简单的Dijkstra写法 基于python

可能是最简单的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}

参考