6.依靠最低费用表 ， 我们再次找出下一个最近距离 ， 并继续对刚刚确认的最近距离节点的邻居数据进行更新 ， 如此往复 ， 直到所有的节点全部更新 ， 也就是最低费用表的所有节点全部找到最近的距离 ， 那算法就完成了 。
我们再看一下整个算法的演示：
算法的整个过程有点像游戏中开战争迷雾 ， 我们只关注眼前的节点 ， 并推算出最近的一个 ， 直到全部找出 。是一种典型的贪婪算法 。
再次强调 。适用于加权非负无环图 。关键字是加权和无环 。
环形图会导致之前确定为最近距离的节点 ， 作为后续节点的邻居被数据更新 ， 而且是更新为比之前大的数值 。也会让程序陷入循环 。
狄克斯特拉算法实现代码 1.有权图的代码实现
graph={}graph['S']={}graph['A']={}graph['B']={}graph['C']={}graph['D']={}graph['F']=Nonegraph['S']['A']=5graph['S']['B']=0graph['A']['C']=15graph['A']['D']=20graph['B']['C']=20graph['B']['D']=35graph['C']['F']=20graph['D']['F']=10
2.最低费用表和父节点表的实现
#实现最低费用表costs={}costs['A']=float('inf')#无穷大costs['B']=float('inf')costs['C']=float('inf')costs['D']=float('inf')costs['F']=float('inf')#实现父节点表parents={}parents['A']=Noneparents['B']=Noneparents['C']=Noneparents['D']=Noneparents['F']=None
3.狄克斯特拉算法的实现
【Dijkstra算法狄克斯特拉算法，《学点算法吧，Python》】def dijkstra(graph,costs,parents,start_node):processed=[]#用于记录最低费用表中 ， 已经找到的最近路径的节点名称# 更新初始节点的邻居for node in graph[start_node].items():# 遍历初始节点邻居距离costs[node[0]] = node[1]# 更新初始节点最低费用表parents[node[0]] = start_node# 更新初始节点邻居的父节点 ， 就是他自己node=find_lowest_node(costs,processed) #找出第一个最近节点while node is not None:#以目前找出的最近的node为起点 ， 更i性能其邻居在最低费用表中的值cost=costs[node] #最便宜节点 距离neighbors=graph[node]if neighbors is not None:#判断节点必须有邻居for neighbor in neighbors.keys():new_cost=cost+graph[node][neighbor]#计算经过 最近节点 到达新节点后的距离if new_cost
4.计算结果展示
加权图：{'S': {'A': 5, 'B': 0}, 'A': {'C': 15, 'D': 20}, 'B': {'C': 20, 'D': 35}, 'C': {'F': 20}, 'D': {'F': 10}, 'F': None}最低费用图：{'A': inf, 'B': inf, 'C': inf, 'D': inf, 'F': inf}父节点图：{'A': None, 'B': None, 'C': None, 'D': None, 'F': None}计算结果：{'A': 5, 'B': 0, 'C': 20, 'D': 25, 'F': 35} {'A': 'S', 'B': 'S', 'C': 'B', 'D': 'A', 'F': 'D'}