在我们寻找身边的人际关系的时候，可以采用上一篇的广度优先搜索来进行查找。当我们走出门去，想要到某个地方的时候，这种场景我们安排路径就更加的适合使用 狄克斯特拉算法。
狄克斯特拉算法是应用于权值为 正 的 加权有向无环图 寻找最短路径的一种算法。
算法过程
加权有向无环图
什么是加权有向无环图呢？形如：
这个就是我们的主角，加权有向无环图。如果你的家住在 Start 处，你想出门去一趟 End，过程中的所有你能走的路径都以箭头的方式标注在图中，所有路径的距离都以数字的方式标注在路径的边上，那么你能找到一条最短的从Start到End的路径吗？
狄克斯特拉算法
我们跟着狄克斯特拉算法的过程，来看狄克斯特拉算法的解决问题的思路。
我们需要一些工具，来完成这个算法：
- 一张记录到达中间地点距离的表格（距离表）
- 一张记录到达该地点的之前的一个节点的表格（父地点表）
- 一张记录所有能走的路径的表格（路径图）
-
站在 Start 处，我们此时只有两条路可以走：A、B，此时我们的这三个图表分别是：
站在Start处.png -
继续找，我们的宗旨是，每次都根据距离表，找最短的路径。比如现在，我们找完了Start，查看一下距离表。此时，距离表告诉我们，此时表中，我们“记录在册”的地点只有两个，A、B，而这两个地点最近的那个是B，距离只有3，所以，我们选择去B。B地点能到达的点只有两个：C、E，此时的三张图表分别为：
站在B处.png
解释一下图中的意思，距离表中，除了我们第一次确定距离的A、B两个点之外，我们从路径图中又得到了可以经由B到达的B点的两个邻居：C、E两点。最终的结果就是，我们从Start（最开始）经由B点所到达的C、E两点的距离分别是：
C：Start -> B -> C（3 + 1 = 4）（到达B点的距离3加上B点到C点的距离1）
D：Start -> B -> E （3 + 6 = 9）（到达B点的距离3加上B点到E点的距离6）
我们将这个距离写入了距离表，就得到了现在的距离表。而C、E两点是从B点走过来，所以C、E两点的父地点表都写入对应的B地点。
此时，B点所能到达的所有点都记录在了距离表中，所以B点的使命完成，我们把B点标记了一个 X ，表示已经处理完毕。
3.此时我们站在了B点，并且将B点所能到达的地点都“记录在册”。此时我们继续寻找路径。我们再次查看距离表（2中的距离表），此时，距离最短的点是C（因为B点已经标记为已处理，所以C点的4的距离是最短的），所以，我们去到C点，C点能到达的点只有End，所以，站到C点之后，我们继续更新三个图表：
跟上面一样，所有C点能到达的点，我们都记录在册了，所以，C的使命完成了，我们把C标记一个 X。
4.我们继续寻找。还是老规矩，我们依然查看距离表，此时，距离表上最短的距离是到达A点的距离5，所以，我们来到A点。A点所能到达的是C、D两点，我们分别登记入册，所以现在的三个图表分别是：
由于之前我们已经处理过C点，所以，即使现在C点还可以到达，但是已经不是最近的可到达距离了（C点到达的最短距离是之前的经由B的距离4，现在经由A到达C的距离是5+2 = 7）。所以我们就不再去记录C了（不再记录已经处理过的点）。
5.我们继续找。还是查看距离表，此时，距离表中，能到达的最近的点是D点（注意：距离表中的距离指的都是从起点到达该点的距离，是7）。此时我们来到D点，D点能到达的点是：C、End，此时我们登记入册（C已经处理过，不入册）我们得到的三个图表分别是：
C点已经处理过了，我我们就不再考虑经由D点去到C点了。我们来看经由D点到达End点，此时，距离表中，从Start可以到达End的距离已经有了一个9，我们此时需要比较一下，经由D到达End的距离是：7 + 4 = 11 < 9。距离表中的距离要小于现在这条经由D点到End的路径，所以，我们不用更新End点的路径和父地点表。但是D点所有能到到达的地方都已经处理完了，所以我们给D打一个X。
-
我们继续找。此时表中除了最终到达的点End之外，只有一个E点了。所以此时最近能到达的点就只有E了，我们来到E点。E点所能到达的点只有：End。我们此时来更新一下距离表（比较距离，看是否需要更新）：
站在E处.png
此时，我们可以看到，E点到达End点的距离是1，所以经由E点到达End点的距离是： 9（到达E点的距离）+ 1（E点到End点的距离） = 10 > 9（表中到达End点的距离），所以我们不用跟新这个距离跟父节点，但是E点所能到达的所有邻居节点已经处理完毕了，所以我们把E点标记为 X。
最终，我们已经处理完毕了图中所有从Start到达End点所经由的点。我们现在查看距离表，此时到达End的距离是9，所以最终所有路径中能到达End点的最小距离就是9。
还有一点，我们要找到这条路径。这点好办，我们查看最终的父地点表，End的父地点是C，我们此时记下： End -> C。我们在看C的父地点是B，此时我们完善记录：End -> C -> B。还没有到Start，我们继续找B的父地点，父地点是：Start！我们终于找到头了，我们记录：End -> C -> B -> Start。此时，我们翻转这条逆向回溯的路径：Start -> B -> C -> End，这条路径就是从Start到达End最短的路径！
注意： 迪克斯特拉算法只能用于权值为正的有向无环图。如果存在负的权值，那么就会造成狄克斯特拉算法中的通过累加来找最小路径的思想。每次的距离只能增加，不能减少才行。必须要是有向无环图才行，要不然找路径的过程就会在环中无限的循环下去，永远出不来。
算法实现
# -*- coding: utf-8 -*-
# @Time : 2018-12-27 12:59
# @Author : Jaedong
# @Version : 3.6
# @File : dijkstra_algorithm.py
# @Software: PyCharm
# 狄克斯特拉算法，获取加权有向无环图中两个点的最小距离
def dijkstra_algorithm(graph, start, end):
# 构建一个从起点开始，记录所有经过节点的路程距离的距离表
distances = {}
# 构建一个记录某个节点的父节点的散列表，方便路径回溯
parents = {}
# 初始化 distances 和 parents
for neighbor in graph[start]:
distances[neighbor] = graph[start][neighbor]
parents[neighbor] = start
# 查漏补缺，需要确定到终点的距离，如果没有的话就是不知道，不直达的话就是无限大
if end not in distances:
distances[end] = float('inf')
parents[end] = None
# 用于记录已经计算完毕到它最短距离的节点
handled = []
node = get_lowest_cost(distances, handled)
while node is not None:
# 获取到达节点的距离
distance = distances[node]
# 通过该节点可到达的节点（邻居节点）
for neighbor in graph[node]:
# 通过节点到达其邻居节点的距离等于到达该节点的距离加上该节点到其邻居节点的距离
new_distance = distance + graph[node][neighbor]
# 如果该节点的邻居节点在记录路程的表中，就看看是否更新一下到它的距离
if neighbor in distances:
# 如果通过该节点到达该节点的邻居节点的距离 小于 其它途径到达该邻居节点的距离
# 就更新到达该节点邻居节点的距离，使到达该邻居节点的距离越小越好，路径就最优
# 如果小于的话，就更新邻居节点的父节点为该节点，也就是选取了到达该邻居节点的
# 更好的路径是通过该节点到达的这一条
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
parents[neighbor] = node
# 如果该节点的这个邻居节点并没有在距离表中，无需更新，就直接添加进去
else:
distances[neighbor] = new_distance
parents[neighbor] = node
# 记录处理过后的节点，继续往前走下去
handled.append(node)
node = get_lowest_cost(distances, handled)
# 更新了所有节点的到达最小距离，那么到达end的最小距离就是distances表中end所对应的值
distance = distances[end]
# 通过不断的回溯的方式，得到end到达start的路径，这样，就得到了start到达end的路径
parent = parents[end]
paths = [parent, end]
while parent is not start:
paths.insert(0, parents[parent])
parent = parents[parent]
return distance, paths
# 获取距离表中到达所需距离最短的节点
def get_lowest_cost(distances, handled):
shortest = float('inf')
shortest_node = None
for node in distances:
if distances[node] < shortest and node not in handled:
shortest = distances[node]
shortest_node = node
return shortest_node
# 构建路径图，使用字典嵌套字典的方式（散列表嵌套散列表）
graph = {}
# 从起点开始，起点可以到达两个点：A、B
graph['Start'] = {}
# 起点到A点的距离是5 Start -> A
graph['Start']['A'] = 5
# 起点到B点的距离是3 Start -> B
graph['Start']['B'] = 3
# A可以到达两个点：C、D
graph['A'] = {}
# ... ...
graph['A']['C'] = 2
graph['A']['D'] = 2
graph['B'] = {}
graph['B']['C'] = 1
graph['B']['E'] = 6
graph['C'] = {}
graph['C']['End'] = 5
graph['D'] = {}
graph['D']['C'] = 3
graph['D']['End'] = 4
graph['E'] = {}
graph['E']['End'] = 1
graph['End'] = {}
distance, paths = dijkstra_algorithm(graph, 'Start', 'End')
print('\n最短的距离是：{}, 路径是： {}'.format(distance, paths))
结果是：
