广度优先搜索，它找出的是段数最少的路径（如第一
个图所示）。如果你要找出最快的路径（如第二个图所示），该如何办
呢？为此，可使用另一种算法——狄克斯特拉算法（Dijkstra'salgorithm）。
image.png
狄克斯特拉算法包含4个步骤。
(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
(2) 更新该节点的邻居的开销，其含义将稍后介绍。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
第一步：找出最方便时间最短的节点。
第二步：计算经节点B前往其各个邻居所需的时间。
第三步：重复！
重复第一步：找出可在最短时间内前往的节点。你对节点B执行了第二步，除节点B外，可在最短时间内前往的节点是节点A。
重复第二步：更新节点A的所有邻居的开销。
你发现前往终点的时间为6分钟！
如果使用广度优先搜索，找到的最短路径将不是这条，因为这条路径包含3段，而有一条从起点到终点的路径只有两段。
术语
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重
（weight）。
下面来看看如何使用代码来实现狄克斯特拉算法。
graph = {}
graph['you'] = ['alice', 'bob', 'claire']
#起点有2个邻居a，b分别表示他们的权重值
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
#要获取起点的所有邻居.
print(graph['start'].keys())
#权重的获取
print(graph["start"]["a"])
print(graph["start"]["b"])
#添加其它邻居
graph['a'] = {}
graph['a']['fin'] = 1
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5
graph['fin'] = {} #终点没有任何邻居
#创建散列表parents
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None
"""
节点的开销指的是从起点出发前往该节点需要多长时间。你知道的，从
起点到节点B需要2分钟，从起点到节点A需要6分钟（但你可能会找到
所需时间更短的路径）。你不知道到终点需要多长时间。对于还不知道
的开销，你将其设置为无穷大。在Python中能够表示无穷大吗？你可以
这样做：infinity = float("inf")
"""
#创建开销
infinity = float("inf")
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = infinity
#一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。
processed = []
def find_lowest_cost_node(costs):
lowest_cost = float('inf')
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost<lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node =node
return lowest_cost_node
node = find_lowest_cost_node(costs) #在未处理的节点中找出开销最小的节点
while node is not None: #这个while循环在所有节点都被处理过后结束
cost = costs[node]
neightbors = graph[node]
for n in neightbors.keys(): #遍历当前节点的所有邻居
new_cost = cost + neightbors[n]
if costs[n]>new_cost: #如果经当前节点前往该邻居更近,
costs[n] = new_cost #就更新该邻居的开销
parents[n] = node #同时将该邻居的父节点设置为当前节点
processed.append(node) #将当前节点标记为处理过
node = find_lowest_cost_node(costs) #找出接下来要处理的节点，并循环
