前言
狄克斯特拉算法是解决加权图求最短路径的算法，广度优先算法可以求非加权图的最短路径，但是如果图的边权重不一样，那么就可以用狄克斯特拉算法来解决。
背景
现有一问题，想要求A到D之间的最短距离，其中每条边的数字代表距离，如下图：
很显然，如果使用广度优先算法是求不出正确结果的。
狄克斯特拉算法描述：
- 找出距离最短的节点，
- 对于该节点的邻居，如果有前往他们更短距离，更新其开销，
- 重复1,2直到所有节点都更新了。
下面我们具体执行这些步骤：
首先建立一张表格，用于存放到达每个节点的开销
更新起点的时候由于还不知道到EFD的距离，因此我们用无穷大表示先。在计算的过程中，我们会不断地更新这张表。另外，为了找到最短路径，我们还需要添加有父节点的列
好，我们开始执行算法：
先找到最便宜的节点，根据我们建立的表格知道，是E，然后计算前往E的邻居的开销，也是就是前往F的。
下一个最便宜的节点是B，更新前往B的令居的开销，也就是更新前往D的开销
重复上述步骤
下一个最便宜的节点是F，更新前往F的令居的开销，也就是更新前往C，D的开销
下一个最便宜的节点是C，更新前往C的令居的开销，也就是更新前往D的开销
所有节点都更新完了，可以确定最短路径了，到D最短总开销是16，路径根据表可知，D的父节点C，C的父节点F，F的父节点E，E的父节点A，那么就是A-E-F-C-D。
算法实现
我们以下面简单的图为例，求从A到D的最短路径
要解决这个问题，需要维护三个散列表（python中dict）：
后面会不断更新cost和parent，
首先实现graph：
graph = {}
graph['A'] = {"B":4,"C":1}
graph['B'] = {"D":3}
graph['C'] = {"B":2,"D":7}
graph['D'] = {}
实现cost：
costs = {}
costs['B'] = 4
costs['C'] = 1
costs['D'] = float('inf') # 表示无穷大
实现parent：
parents = {}
parents['B'] = 'A'
parents['C'] = 'A'
parents['D'] = None
最后需要一个list用于记录处理过的节点
processed = []
数据结构都建好了，那么我们按怎样的算法步骤执行呢，步骤：
- 获取离开始节点最近的节点
- 更新这个节点的邻居开销
- 如果有邻居被更新，那么同时更新其父节点
- 将该节点标记为处理过，并重复执行以上步骤，直到所有节点都已这样处理。
下面根据算法步骤列出代码：
graph = {}
graph['A'] = {"B":4,"C":1}
graph['B'] = {"D":3}
graph['C'] = {"B":2,"D":7}
graph['D'] = {}
costs = {}
costs['B'] = 4
costs['C'] = 1
costs['D'] = float('inf') # 表示无穷大
parents = {}
parents['B'] = 'A'
parents['C'] = 'A'
parents['D'] = None
processed = []
def get_min_cost_node(costs):
min_cost = float('inf')
min_cost_node = None
for n in costs:
cost = costs[n]
if cost < min_cost and n not in processed:
min_cost = cost
min_cost_node = n
return min_cost_node
node = get_min_cost_node(costs) # 在未处理的节点中找到开销最小的节点
while node is not None:
cost = costs[node]
neighbs = graph[node]
for n in neighbs: # 遍历当前节点的所有邻居
new_cost = cost + neighbs[n]
if costs[n] > new_cost: # 如果经由当前节点前往该邻居更近 就更新该邻居的开销
costs[n] = new_cost
parents[n] = node # 同时更新该邻居节点的父节点
processed.append(node) # 将节点加入到已处理队列
node = get_min_cost_node(costs) # 找到下一步要处理的节点
print(processed) #求出最短路径
附录
参考《算法图解》
