从一个小例子理解狄克斯特拉算法

简介

狄克斯特拉算法解决了有向图最短路径的问题。

基本思路

狄克斯特拉算法包含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)