算法图解：第七章 狄克斯特拉算法 dijkstra
加权图-提高或降低某些边的权重；
狄克斯特拉算法，找出加权图中的最短路径；
环，使该算法失效，（待核实：环会导致无限循环的问题）
上一章广度优先搜索从双子峰到金门桥有最短路径，采用本章算法能找出最快路径。
狄克斯特拉算法
1.找出最便宜的节点，即可在最短时间内到达的节点
2.更新该节点的邻居开销：对于该节点的邻居，检查是否有前往它们的最短路径，有则更新其开销
3.重复该过程，直到遍历完所有节点
4.计算最终路径
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重。
带权重的图为加权图，不带权重的图为非加权图。
换钢琴，创建开销表
第一步，乐谱可以换黑胶唱片和海报，海报为最便宜的节点
第二步，确定该节点的邻居，吉他、架子鼓，但到吉他，架子鼓的最短路径不为海报，为黑胶唱片，将该步父节点更新为黑胶唱片
第三步，吉他和架子鼓都能到达终点钢琴，架子鼓为最短路径，父节点为架子鼓。
反向推导：钢琴的父节点为架子鼓，架子鼓的父节点为黑胶唱片，黑胶唱片的父节点为乐谱。
沿父节点回溯，可得到完整的交换路径。
注：上述最短路径为让某种度量指标最少。
负权边：权重为负的边，狄克斯特拉不能用于包含负权边的图。该算法只能找确定当前节点邻居节点的最短开销，如果该节点有其他路径可达到最短开销则找不到，负权边会导致该算法遗漏最优解。
负权边的图可用另一种算法：贝尔曼-福德算法
代码实现：
循环条件：待处理节点不为空
1.获取离起点最近的节点
2.更新其邻居开销
3.如果有邻居开销被更新，同时更新其父节点
4.将该节点标记为处理过
准备：
三个散列表：GRAPH、COSTS、PARENTS
随着算法进行，不断更新costs、parents
存储起点：
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”] = {}
costs表用于存储每个节点的开销
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):
lowcost_cost = float(“inf”)
lowcost_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed;
lowcost_cost = cost
lowcost_cost_node = node
return lowest_cost_node
具体算法：
node = find_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neighbor = graph[node]
for n in neighbor.keys():
new_cost = cost + neighbor[n]
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
