狄克斯特拉算法
思路：
找到未被处理的节点
获取距离起点最近的节点，更新其邻居的开销
如果有邻居的开销被更新，那么同时更新其父节点
将其标记为已经处理过，然后继续处理那些未被处理过的节点
#建立三张散列表。graph 存储关系图；costs 存储各个节点的开销（开销是指从起点到该节点的最小的权重）；parents 存储各个节点的父节点是谁。
#创建一个数组用来存储已经处理过的节点 processed.
#BFS查找两点之间的最短路径，解决的“段数”最少
#Dijkstra 狄克斯特拉算法解决的是总权重最小的路径，一般解决加权图中的最短路径问题
#这个算法只适用于有向无环图，而且只能用于边权为正的图，不能用于负边权的图中
# 核心代码，算法实现
#找到最小开销，并更新
#也就是说，该函数的功能就是找出在未处理的节点中的最小节点
def find_lowest_cost_node(costs):
#float("inf") 表示正向无穷，一般我们对与节点到终点的位置距离定义为正向无穷
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs: #遍历所有的节点
cost = costs[node]
#如果当前的节点开销更低而且没有被处理过，那么更新这个节点的开销
if (str(cost) <str(lowest_cost)) and node not in processed:
lowest_cost = node
lowest_cost_node = node
return lowest_cost_node
node = find_lowest_cost_node(costs)#在未处理的节点中，找出开销最小的节点
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():#遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
#如果经历这个节点前往邻居更近，那么就更新邻居的开销，同时将邻居的父节点设为当前节点
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = node
#将处理过的节点加入列表processed
processed.append(node)
#找出下一个要处理的节点
node = find_lowest_cost_node(costs)
注意一下这个算法的使用范围
- 一般解决有权图的最短路径问题
- 注意边权不能为负数
- 而且这个算法只适用于有向无环图
- 而且注意这个里边所提及到的最短路径问题，这里不一定是物理距离，可能是用时最短等某种量度上的指标最小
