算法图解-狄克斯特拉算法

• 在之前的广度优先搜索中,可以找出了从A点到B点的最短路径。

  
  0-1

• 这是最短路径，因为段数最少——只有三段，但不一定是最快路径。如果给这些路段加上时间，你将发现有更快的路径。

  
  0-2
• 之前用了广度优先搜索，它找出的是段数最少的路径（如第一个图所示）如果你要找出最快的路径（如第二个图所示），该如何办呢？为此，可使用另一种算法——狄克斯特拉算法（Dijkstra’s algorithm）

1. 使用狄克斯特拉算法
   1-1
   其中每个数字表示的都是时间，单位分钟。为找出从起点到终点耗时最短的路径，你将使用
   狄克斯特拉算法。
   如果你使用广度优先搜索，将得到下面这条段数最少的路径。
   1-2
   这条路径耗时7分钟。下面来看看能否找到耗时更短的路径！狄克斯特拉算法包含4个步骤。
   (1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
   (2) 更新该节点的邻居的开销，其含义将稍后介绍。
   (3) 重复这个过程，直到对图中的每个节点都这样做了。
   (4) 计算最终路径。
   第一步：找出最便宜的节点。你站在起点，不知道该前往节点A还是前往节点B。前往这两
   个节点都要多长时间呢？
   1-3 1-4

前往节点A需要6分钟，而前往节点B需要2分钟。至于前往其他节点，你还不知道需要多长时间。
由于你还不知道前往终点需要多长时间，因此你假设为无穷大（这样做的原因你马上就会明白）。节点B是最近的——2分钟就能达到。
第二步：计算经节点B前往其各个邻居所需的时间。

1-5
你刚找到了一条前往节点A的更短路径！直接前往节点A需要6分钟。
1-6
但经由节点B前往节点A只需5分钟！
1-7
对于节点B的邻居，如果找到前往它的更短路径，就更新其开销。在这里，你找到了：

• 前往节点A的更短路径（时间从6分钟缩短到5分钟）；
• 前往终点的更短路径（时间从无穷大缩短到7分钟）。

第三步：重复！
重复第一步：找出可在最短时间内前往的节点。你对节点B执行了第二步，除节点B外，可
在最短时间内前往的节点是节点A。

1-8
重复第二步：更新节点A的所有邻居的开销。
1-9
你发现前往终点的时间为6分钟！
你对每个节点都运行了狄克斯特拉算法（无需对终点这样做）。现在，你知道：

• 前往节点B需要2分钟；
• 前往节点A需要5分钟；
• 前往终点需要6分钟。
  1-10
  广度优先搜索查找的是两点之间的最短路径，“最短路径”的意思是
  段数最少。在狄克斯特拉算法中，给每段都分配了一个数字或权重，因此狄克斯特拉算法找出
  的是总权重最小的路径。
  对比

2. 术语
   狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。
   2-1
   带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。
   2-2
   要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。图还可能有环，而环类似下面这样。
   2-3
   2-4

3. 代码实现

• 以下面的图为例

  
  3-1

• 要编写解决这个问题的代码，需要三个散列表。

  
  3-2

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"] = {}
# 创建开销表的代码如下：
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# 存放父节点的字典
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 最后，你需要一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。
processed = []
# print(graph)
def find_lowest_cost_node(costs):
    "在未处理的节点中找出开销最小的节点"
    lowest_cost = float("inf")
    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
node = find_lowest_cost_node(costs)
while node is not None: # 这个while循环在所有节点都被处理过后结束
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys(): # 遍历当前节点的所有邻居
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: # 如果经当前节点前往该邻居更近
            costs[n] = new_cost # 就更新该邻居的开销
            parents[n] = node # 同时将该邻居的父节点设置为当前节点
    processed.append(node) # 将当前节点标记为处理过
    node = find_lowest_cost_node(costs) # 找出接下来要处理的节点，并循环
print(processed)

4. 小结

• 广度优先搜索用于在非加权图中查找最短路径。
• 狄克斯特拉算法用于在加权图中查找最短路径。
• 仅当权重为正时狄克斯特拉算法才管用。
• 如果图中包含负权边，请使用贝尔曼-福德算法。