离散课上图论的时候讲了理论知识,但是还没实践过,于是拿python写了一下,顺便做个笔记防止忘记。
python自带的数据结构比较丰富,写起来的确顺滑很多,太香了md
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)