《算法图解》之狄克斯特拉算法

说明：以下内容均参考：[美]Aditya Bhargava所著的《算法图解》

广度优先搜索只解决了路径最短问题，但如果给这些路径加上权（即考虑加权图），计算加权最短路径时，BFS就无能为力了，此时就要借助另外一种算法：狄克斯特拉算法（Dijkstra's algorithm）。

不带权的图称为非加权图。

无向图等价于双向图，无向图中任意两个邻居都互为邻居，因此无向图中的每条边实际上都是一个环。

BFS只适用于无权图。

狄克斯特拉算法只适用于正加权的有向无环图（directed acyclic graph，DAG）。

如果有负权边，狄克斯特拉算法将会失效。因为狄克斯特拉算法认为：节点的开销一旦被更新，就意味着没有前往该节点的开销更小的路径，而这种假设仅当没有负权边存在时才成立。因此狄克斯特拉算法不能用于包含负权边的图。

贝尔曼 - 福德算法（Bellman - Fold algorithm）可用于在包含负权边的图中找出最短路径。

注意：这里的“路径”不一定指的是物理上的距离，也可以是其他的度量方法，如价格、时间等。

狄克斯特拉算法包含4个步骤：

（1）找出“开销最小”的节点（对未知的节点，先假设其开销为无穷大）；

（2）对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新该节点的邻居的开销；

（3）重复第（1）（2）步，直至对图中的每个节点都这样做了（无需对终点这样做）；

（4）计算最终路径。

狄克斯特拉算法的代码实现：

以图4-1所示的图为例。

图4-1

为实现这一算法，需要准备3个字典：

（1）graph字典：用于存储每一个起点和该起点的所有邻居以及该起点其每一个邻居的开销，该字典一旦被创建，在整个算法运行的过程中都不再改变；

（2）costs字典：用于存储从最初的起点开始到每一个节点的开销（初始化时只有到起点邻居的开销是可以确定的，除此之外到其他所有节点的开销都设为无穷），该字典会不断更新，以保证更新过的开销是所有路径中能取到的最小开销；

（3）parents字典：配合costs字典使用，用于存储每一个节点的父节点，该字典也会不断更新，更新后的父节点是能够取到最小开销的父节点。

这3个字典的图示如图4-2所示。

图4-2：狄克斯特拉算法中用到的3个字典

由于带有权重，因此在构建graph字典时要使用“字典中的字典”（见代码）。

'''
准备工作
'''
# 构造全图字典graph
graph = {}

graph['start'] = {} # 使用字典中的字典
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['final'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['final'] = 5

graph['final'] = {} # 终点没有任何邻居，因此只用一个空字典表示

# 构造开销字典costs
infinity = float('inf') # python中无穷大的表示
costs = {}
costs['a'] = 6 # 初始时从起点到A、B以及终点的开销分别是6、2和无穷
costs['b'] = 2
costs['final'] = infinity

# 构造父节点字典parents
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['final'] = None # 开始时，并不知道终点的父节点是谁

# 还需要一个额外的数组，用于记录已经处理过的节点（避免重复处理节点）
processed = []


'''
代码的主体部分
'''
# 寻找开销最小的节点的函数定义如下：
def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None
    for node in costs: # 遍历costs中所有存储的节点
        cost = costs[node] # 取节点对应的总开销
        if cost < lowest_cost and node not in processed: # 不断查找直至找到开销最小且没有被处理过的节点
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node # 这个函数最终返回的是一个节点的名称

# 注意：在Python中，函数必须先定义然后才能调用，否则会报错
# 在未处理的节点中找出开销最小的节点
node = find_lowest_cost_node(costs) # 这里node取出来的是costs中的键，即对应的节点的名称
while node is not None: # 循环终止的条件是所有的节点都已被处理过
    cost = costs[node] # 这里取出来的是costs中的值，即node节点对应的总开销（从最初起点开始到node的开销）
    neighbors = graph[node] # graph中存的是字典中的字典，因此这里取出来的是大图中node节点的所有邻居及其开销
    for key in neighbors.keys(): # 遍历node节点的所有邻居
        new_cost = cost + neighbors[key] # node节点的该邻居key的新的总开销（指的是从最初的起点到key节点的
                                         # 总开销）是node节点的总开销cost + 大图中node节点到key的开销
        if costs[key] > new_cost: # 如果costs中存储的关于key的总开销比这个新算出来的总开销大，
            costs[key] = new_cost # 那么就用这个新算出来的更小的总开销替换原来的总开销，
            parents[key] = node   # 同时，更新key节点的父亲
    processed += [node] # 当node节点的所有邻居都被处理完后，就将该节点标记为处理过了，
    node = find_lowest_cost_node(costs) # 然后寻找下一个要处理的node节点

这样，当程序运行完后，costs['final']中就保存了从最初的起点到终点的最小开销，从parents中final的父节点开始，不断往前回溯，即可找到使得开销最小的路径。

整个算法可以看做是：正向传播找最小开销，反向回溯寻最短路径。（这里的最短指加权最短）