最短路径问题：重新发明 Dijkstra 算法

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

By Long Luo

本科时在 电子科大 学的专业是 通信工程[1] ，计算机网络[2] 是必修课。在学习网络层的路由协议时，Dijkstra\textit{Dijkstra} [3] 算法是必须要掌握的。不过读书时，对这个算法是懵懵懂懂的，当时是死记硬背记住的，并没有理解其原理，过了一段时间之后就完全忘记了。如今在 2022 年我重新学习 搜索算法[4] 时，已经彻底理解 Dijkstra\textit{Dijkstra} 算法了。更确切的说，如果我们掌握了其原理，我们也可以重新发明 Dijkstra\textit{Dijkstra} 算法，就让我们从一个自驾游例子开始吧！

到达目的地哪条路径最快？

假期时，我们想从深圳自驾去上海，怎么去呢？打开地图软件，地图会给你规划好几条路线，在找到这些路线的背后就用到了 A Star\textit{A Star}[5] 算法 或者 Dijkstra\textit{Dijkstra} 算法，它们都属于 最短路径算法[6] 。这个例子解释 用来Dijkstra\textit{Dijkstra} 算法并不是特别好，但方便大家理解。

假如回到那个 2G 时代，没有导航软件只有一张地图，大家会怎么做呢？

我们可能要根据到高速和城市之间里程来计算，比如北上赣州，经南昌、杭州到上海和经福建、温州、宁波再到上海哪个更快，不同城市之间高速路况情况，每段之间耗时多长，最后得到了一条路线。虽然大部分人并不知道 Dijkstra\textit{Dijkstra} 算法，但并不妨碍我们天生就会用 Dijkstra\textit{Dijkstra} 算法，所以我们把这个思考过程写下来，实际上就是 Dijkstra\textit{Dijkstra} 算法。

让我们重新一步一步来发现 Dijkstra\textit{Dijkstra} 算法吧！

从 BFS 开始

由于找合适的国内城市路线图和制图太花时间，刚好维基上的 Breadth-first search algorithm[7] 的页面上就提供了德国国内城市地图的例子，这里就借用下，如下图所示：

Germany Map

图1. 德国城市地图

如果我们从 法兰克福(Frankfurt) 出发，很容易得到到达各个城市的最快方式，如下图所示：

Germany BFS

以下面这个动图为例，我们来看看 BFS\textit{BFS} 是如何做的？

bfs

从上图可以看出，BFS\textit{BFS} 的运行过程可以描述如下：

  1. 首先选择一个顶点作为起始结点，并将其染成蓝色，其余未访问结点为黑色；
  2. 将起始结点放入队列中；
  3. 从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部，将已访问过结点涂成蓝色，没访问过的结点是黑色。如果顶点的颜色是蓝色，表示已经发现并且放入了队列，如果顶点的颜色是黑色，表示还未访问；
  4. 按照同样的方法处理队列中的下一个结点，直到所有节点都访问完毕。

伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure BFS(G, source) is
      let Q be a queue
      label source as explored
	  
      Q.enqueue(source)
	  
      while Q is not empty do
          v := Q.dequeue()
		  
          if v is the goal then
              return v
        
          for all edges from v to w in G.adjacentEdges(v) do
              if w is not labeled as explored then
                  label w as explored
                  w.parent := v
                  Q.enqueue(w)

BFS 的问题在哪里？

在现实生活中，图1的德国城市地图其实是不符合实际的，因为不同城市都是连接在一起，构成了一张网。法兰克福(Frankfurt)和斯图加特(Stuttgart)可能就有直连的高速公路，这里不妨设距离为 300km300km 。

从 法兰克福(Frankfurt) 出发到 斯图加特(Stuttgart)，可以直达也可以经 卡塞尔(Kassel) 到 斯图加特(Stuttgart) 。假如 卡塞尔(Kassel) 到 斯图加特(Stuttgart) 只有 20km20km 的话，那么这条路线就是从 法兰克福(Frankfurt) 到 斯图加特(Stuttgart) 的最短路径。

为了减少后续书写时间，我们用 dF→Sd_{F \to S} 来表示从 法兰克福(Frankfurt) 到 斯图加特(Stuttgart) 的距离。

但如果直接用 BFS\textit{BFS} 算法去做的话，我们计算得到的 min⁡dF→S=300km\min {d_{F \to S}} = 300km ，而不是

dF→S=dF→K+dK→S=173+20=193kmd_{F \to S} = d_{F \to K} + d_{K \to S} = 173 + 20 = 193km

那么用 BFS\textit{BFS} 求最短路径问题出在哪里呢？

我们可能会想到遍历顺序影响了答案，假如我们先遍历到 卡塞尔(Kassel)，然后就可以发现 min⁡dF→S=193km\min {d_{F \to S}} = 193km 。但在 BFS\textit{BFS} 中，我们会发现我们无法再去遍历 斯图加特(Stuttgart)，因为在遍历 法兰克福(Frankfurt) 时，斯图加特(Stuttgart) 作为 法兰克福(Frankfurt) 的邻居节点已经遍历了，所以我们无法再次遍历 斯图加特(Stuttgart)了！

BFS\textit{BFS} 作为和 DFS\textit{DFS}[8] 齐名的遍历算法，此时此刻束手无策了！

是的，时代变了， BFS\textit{BFS} 你需要改变！

时代变了，拥抱变化的 BFS

回到 BFS\textit{BFS} 的代码中，我们发现是下面这行代码阻止了我们再次访问 斯图加特(Stuttgart) ：

1
2
if w is not labeled as explored then
	# visit neighbor

但是我们又需要记录每个节点的遍历状态，要不然程序会陷入死循环中。那么我们怎么才能再次遍历某个节点呢？

当…当…当…！

答案很简单，如果我们发现了一条更好的路径时，我们就可以再次访问这个节点。

我们使用一个数组 dist\textit{dist} 存储源节点到每个节点的距离，初始设置 dist[i]\textit{dist[i]} 为无穷大，如果发现当前节点 cost\textit{cost} 更低时，就遍历该节点并更新 dist[i]\textit{dist[i]} ，伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
procedure New_BFS(G, source) is
      let Q be a queue

	  dist[source] = 0 
	  
      for each vertex v in G:
          if v != source
			dist[v] = INF        // Unknown distance from source to v              

      Q.enqueue(source)
	  
      while Q is not empty do
          v := Q.dequeue()
		  
          if v is the goal then
              return v
        
          for all edges from v to w in G.adjacentEdges(v) do
			  new_cost = compute_cost()
              if new_cost < dist[w]:  # find a better path!
			      dist[w] = new_cost
                  Q.enqueue(w)

呼之欲出的 Dijkstra\textit{Dijkstra} 算法

用一个动画来描述上一章中优化的 BFS\textit{BFS} 算法，如下图所示：

Dijkstra_Animation

Dijkstra Animation

通过上面对 BFS\textit{BFS} 的优化，我们已经很接近 Dijkstra\textit{Dijkstra} 算法了！如果我们我们把队列 QQ 改成 PriorityQueue\textit{PriorityQueue} 的话， PQPQ 存储的对象为 [v,dist[v]][v, dist[v]] ，并根据 dist[v]\textit{dist[v]} 排序的最小堆，伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
procedure Dijkstra(G, source) is
	  let PQ be a priority queue
	  
	  dist[source] = 0 
	  
      for each vertex v in G:
          if v != source
			dist[v] = INF        // Unknown distance from source to v              

      PQ.enqueue(source, dist[source])
	  
      while PQ is not empty do
          v := PQ pop the min
		  
          if v is the goal then
              return v
        
          for all edges from v to w in G.adjacentEdges(v) do
			  new_cost = compute_cost()
              if new_cost < dist[w]:  # find a better path!
			      dist[w] = new_cost
                  PQ.enqueue(w, dist[w])

到这里，你有没有意识到，实际上我们已经重新发明了一遍 Dijkstra\textit{Dijkstra} 算法呢？

如果我们早生几十年，抢在 Edsger Wybe Dijkstra [9] 老爷子在 1956 年之前先发表这个算法，也许这个算法的名字就冠于我们的名字了呢？😄

参考资料

  1. 通信工程专业是做什么的？ ↩︎

  2. 计算机网络：自顶向下方法 ↩︎

  3. Dijkstra Algorithm ↩︎

  4. Search algorithm ↩︎

  5. A* search algorithm ↩︎

  6. Shortest path problem ↩︎

  7. Breadth-first search ↩︎

  8. Depth-first search ↩︎

  9. Edsger W. Dijkstra ↩︎