python 狄克斯特拉算法

前言

狄克斯特拉算法是解决加权图求最短路径的算法，广度优先算法可以求非加权图的最短路径，但是如果图的边权重不一样，那么就可以用狄克斯特拉算法来解决。

背景

现有一问题，想要求A到D之间的最短距离，其中每条边的数字代表距离，如下图：

很显然，如果使用广度优先算法是求不出正确结果的。
狄克斯特拉算法描述：

1. 找出距离最短的节点，
2. 对于该节点的邻居，如果有前往他们更短距离，更新其开销，
3. 重复1,2直到所有节点都更新了。

下面我们具体执行这些步骤：
首先建立一张表格，用于存放到达每个节点的开销

更新起点的时候由于还不知道到EFD的距离，因此我们用无穷大表示先。在计算的过程中，我们会不断地更新这张表。另外，为了找到最短路径，我们还需要添加有父节点的列

好，我们开始执行算法：

先找到最便宜的节点，根据我们建立的表格知道，是E，然后计算前往E的邻居的开销，也是就是前往F的。

下一个最便宜的节点是B，更新前往B的令居的开销，也就是更新前往D的开销

重复上述步骤
下一个最便宜的节点是F，更新前往F的令居的开销，也就是更新前往C，D的开销

下一个最便宜的节点是C，更新前往C的令居的开销，也就是更新前往D的开销

所有节点都更新完了，可以确定最短路径了，到D最短总开销是16，路径根据表可知，D的父节点C，C的父节点F，F的父节点E，E的父节点A，那么就是A-E-F-C-D。

算法实现

我们以下面简单的图为例，求从A到D的最短路径

要解决这个问题，需要维护三个散列表（python中dict）：

后面会不断更新cost和parent，
首先实现graph：

graph = {}
graph['A'] = {"B":4,"C":1}
graph['B'] = {"D":3}
graph['C'] = {"B":2,"D":7}
graph['D'] = {}

实现cost：

costs = {}
costs['B'] = 4
costs['C'] = 1
costs['D'] = float('inf') # 表示无穷大

实现parent：

parents = {}
parents['B'] = 'A'
parents['C'] = 'A'
parents['D'] = None

最后需要一个list用于记录处理过的节点

processed = []

数据结构都建好了，那么我们按怎样的算法步骤执行呢，步骤：

1. 获取离开始节点最近的节点
2. 更新这个节点的邻居开销
3. 如果有邻居被更新，那么同时更新其父节点
4. 将该节点标记为处理过，并重复执行以上步骤，直到所有节点都已这样处理。

下面根据算法步骤列出代码：

graph = {}
graph['A'] = {"B":4,"C":1}
graph['B'] = {"D":3}
graph['C'] = {"B":2,"D":7}
graph['D'] = {}

costs = {}
costs['B'] = 4
costs['C'] = 1
costs['D'] = float('inf') # 表示无穷大

parents = {}
parents['B'] = 'A'
parents['C'] = 'A'
parents['D'] = None

processed = []

def get_min_cost_node(costs):
    min_cost = float('inf')
    min_cost_node = None
    for n in costs:
        cost = costs[n]
        if cost < min_cost and n not in processed:
            min_cost = cost
            min_cost_node = n
    return min_cost_node

node = get_min_cost_node(costs)  # 在未处理的节点中找到开销最小的节点
while node is not None:
    cost = costs[node]
    neighbs = graph[node]
    for n in neighbs:  # 遍历当前节点的所有邻居
        new_cost = cost + neighbs[n]
        if costs[n] > new_cost:  # 如果经由当前节点前往该邻居更近 就更新该邻居的开销
            costs[n] = new_cost
            parents[n] = node  # 同时更新该邻居节点的父节点
    processed.append(node)  # 将节点加入到已处理队列
    node = get_min_cost_node(costs)  # 找到下一步要处理的节点

print(processed)  #求出最短路径

附录

参考《算法图解》