Dijkstra 算法的 python 实现

mymap = {
    1:{1:0,3:10,5:30,6:100},
    2:{2:0,3:5},
    3:{3:0,4:50},
    4:{4:0,6:10},
    5:{4:20,5:0,6:60},
    6:{6:0}
}
max_len = 1000000

T = set() #完成最短路搜索的点集
dis = {} #起始点到其它点的距离，初始化无穷
for i in mymap.keys(): #把max_len视作无穷大
    dis[i] = max_len

start = int(input("strat:"))
end = int(input("end:"))
dis[start] = 0 #初始化源点

def get_min_key(dis:dict): #检索出T集合外的最短路
    _min_k = 0
    _min_v = max_len
    for i in dis.keys():
        if dis[i]<=_min_v and i not in T:
            _min_k = i
            _min_v = dis[i]
    return _min_k

def dijkstra(end):
    while len(T)<len(mymap): #当所有点的最短路找到后结束循环
        _min_k = get_min_key(dis)
        T.add(_min_k) #取出T集合外dis的最小值做最短路
        '''到下一个点的最短路就是一条最短路，因为如果有两条路的权加起来更短，则第一条路就要是最短的'''
        for i in mymap[_min_k].keys(): #遍历该点所有相邻点找更短路
            if dis[_min_k] + mymap[_min_k][i] < dis[i] and i not in T: #有更短路则更新当前dis
                dis[i] = dis[_min_k] + mymap[_min_k][i]
    print(dis[end]) if dis[end]!=max_len else print("+∞")

dijkstra(end)