广度优先搜索找出的是最短路径（无权重），而Dijkstra算法找出的是最快路径（有权重，即权重总和最少的路径）。此只适用于有向无环图。
不能将此算法用于包含负权边的图。
需要三个散列表：
随着算法进行，将不断更新散列表costs和parents
1 首先创建一个散列表：
2 起点有两个邻居A和B，散列表需要同时存储邻居和前往邻居的开销，如何表示呢：
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
即graph[“start”]是一个散列表（即散列表中包含散列表）
要获取起点的所有邻居，可以这样做：
结果如下：
有一条从起点到A的边，还有一条从起点到B的边。如何获得权重：
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"] = {}#终点没有任何邻居
接下来需要用一个散列表来存储每个节点的开销。
节点的开销指的是从起点出发前往该节点需要多长时间。
从起点到B需要2分钟，到A需要6分钟，到终点的时间不知道，设为无穷。
创建开销表：
infinity = float("inf")#无穷
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
还需要一个存储父节点的散列表：
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
最后需要一个数组，用于记录处理过的点，因为对于同一个节点不用处理多次。
算法流程：
完整代码：
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}#终点没有任何邻居
infinity = float("inf")#无穷
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
processed = []
def find_lowest_cost_node(costs):
'''
从未被处理的节点中找出最低开销节点
:param costs: 开销表
:return: 最低开销节点
'''
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:#此循环在所有节点被处理过后结束
cost = costs[node]#此节点的开销
neighbors = graph[node]#此节点的邻居，neighbors是一个散列表
for n in neighbors.keys():#遍历邻居
new_cost = cost + neighbors[n]#开销指的是 从起点到该节点需要多长时间，而不是从当前节点直接前往邻居节点
if costs[n] > new_cost:#原来直接前往此邻居的开销 和 经过此节点前往该邻居的开销对比
costs[n] = new_cost#更新邻居开销
parents[n] = node#将该邻居父节点设为当前节点
processed.append(node)#将该节点标记为处理过
node = find_lowest_cost_node(costs)#找出接下来要处理的节点
print(parents)
print(costs)
最终可以从costs表中看到，fin的开销为6
从parents表的父节点路径为fin-a-b-start
练习：
graph = {}
graph["start"] = {}
graph["start"]["a"] = 2
graph["start"]["b"] = 5
graph["a"] = {}
graph["a"]["b"] = 8
graph["a"]["d"] = 7
graph["b"] = {}
graph["b"]["c"] = 4
graph["b"]["d"] = 2
graph["c"] = {}
graph["c"]["fin"] = 3
graph["c"]["d"] = 6
graph["d"] = {}
graph["d"]["fin"] = 1
graph["fin"] = {}#终点没有任何邻居
infinity = float("inf")#无穷
costs = {}
costs["a"] = 2
costs["b"] = 5
costs["c"] = infinity
costs["d"] = infinity
costs["fin"] = infinity
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["c"] = None
parents["d"] = None
parents["fin"] = None
processed = []
def find_lowest_cost_node(costs):
'''
从未被处理的节点中找出最低开销节点
:param costs: 开销表
:return: 最低开销节点
'''
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:#此循环在所有节点被处理过后结束
cost = costs[node]#此节点的开销
neighbors = graph[node]#此节点的邻居，neighbors是一个散列表
for n in neighbors.keys():#遍历邻居
new_cost = cost + neighbors[n]#开销指的是 从起点到该节点需要多长时间，而不是从当前节点直接前往邻居节点
if costs[n] > new_cost:#原来直接前往此邻居的开销 和 经过此节点前往该邻居的开销对比
costs[n] = new_cost#更新邻居开销
parents[n] = node#将该邻居父节点设为当前节点
processed.append(node)#将该节点标记为处理过
node = find_lowest_cost_node(costs)#找出接下来要处理的节点
print(parents)
print(costs)
最终可以从costs表中看到，fin的开销为8
从parents表看出父节点路径为fin-d-b-start