简介
狄克斯特拉算法解决了有向图最短路径的问题。
基本思路
狄克斯特拉算法包含4个步骤。
(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
(2) 更新该节点的邻居的开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
图解算法
上图中包括6个节点，箭头表示方向，线上的数字表示耗费时间。
首先根据上图做出一个初始表(父节点代表从哪个节点到达该节点)：
初始表
然后从start开始，根据图中的信息更新一下表，由于从start不能直接到达C和End节点，所以耗时为∞(无穷大)：
start
有了这个表我们可以根据算法的步骤往下进行了。
第一步：找出“最便宜”的节点，这里是节点B：
B节点
第二步：更新该节点的邻居的开销，根据图从B出发可以到达C和End节点，B目前的消耗2+B到C的消耗1=3，3小于原来C的消耗∞，所以更新节点C相关的行：
更新C
同理，B目前消耗2+B到End的消耗7=9，小于∞，更新End节点行：
更新End
B节点关联的节点已经更新完成，所以B节点不在后面的更新范围之内了：
B节点除外
找到下一个消耗最小的节点，那就是C节点：
C节点
根据C节点的消耗更新关联节点，只有End节点行被更新了：
更新End节点
这时候C节点也不在更新节点范围之内了：
C节点除外
最后只剩下A节点了，根据A节点的消耗没有更新任何行：
A节点
最终表的数据如下：
最终表
根据最终表，从Start到End的最少消耗是8，路径是Start->B->C->End.
代码实现
graph = {}
graph["Start"] = {}
graph["Start"]["A"] = 6
graph["Start"]["B"] = 2
graph["A"] = {}
graph["A"]["End"] = 4
graph["B"] = {}
graph["B"]["C"] = 1
graph["B"]["End"] = 7
graph["C"] = {}
graph["C"]["A"] = 4
graph["C"]["End"] = 5
infinity = float("inf")
costs = {}
costs["A"] = 6
costs["B"] = 2
costs["C"] = infinity
costs["End"] = infinity
parents = {}
parents["A"] = "Start"
parents["B"] = "Start"
parents["C"] = None
parents["End"] = None
def findLowestCostNode(costs, processed):
lowest_cost = infinity
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
def Dijkstra():
processed = []
node = findLowestCostNode(costs, processed)
while node is not None and node != "End":
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if new_cost < costs[n]:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = findLowestCostNode(costs, processed)
Dijkstra()
print(costs)
print(parents)
