最短路径问题：重新发明 Dijkstra 算法
By Long Luo
大学时学通信专业课程 计算机网络1 时，需要学习 TCP/IP 协议族 2 。在学习网络层的路由协议时， \(\textit{Dijkstra}\) 3 算法是必须要掌握的。不过读书时，对这个算法是懵懵懂懂的，当时是死记硬背记住的，并没有理解其原理，过了一段时间之后就完全忘记了。如今在 2022 年我重新学习 搜索算法4 时，已经彻底理解 \(\textit{Dijkstra}\) 算法了。更确切的说，如果我们掌握了其原理，我们也可以重新发明 \(\textit{Dijkstra}\) 算法，就让我们从一个自驾游例子开始吧！
到达目的地哪条路径最快？
假期时，我们想从深圳自驾去上海，怎么去呢？打开地图软件，地图会给你规划好几条路线，在找到这些路线的背后就用到了 \(\textit{A Star}\)5 算法 或者 \(\textit{Dijkstra}\) 算法，它们都属于 最短路径算法6 。这个例子解释 用来\(\textit{Dijkstra}\) 算法并不是特别好，但方便大家理解。
假如回到那个 2G 时代，没有导航软件只有一张地图，大家会怎么做呢？
我们可能要根据到高速和城市之间里程来计算，比如北上赣州，经南昌、杭州到上海和经福建、温州、宁波再到上海哪个更快，不同城市之间高速路况情况，每段之间耗时多长，最后得到了一条路线。虽然大部分人并不知道 \(\textit{Dijkstra}\) 算法，但并不妨碍我们天生就会用 \(\textit{Dijkstra}\) 算法，所以我们把这个思考过程写下来，实际上就是 \(\textit{Dijkstra}\) 算法。
让我们重新一步一步来发现 \(\textit{Dijkstra}\) 算法吧！
从 BFS 开始
由于找合适的国内城市路线图和制图太花时间，刚好维基上的 Breadth-first search algorithm7 的页面上就提供了德国国内城市地图的例子，这里就借用下，如下图所示：
如果我们从 法兰克福(Frankfurt) 出发，很容易得到到达各个城市的最快方式，如下图所示：
以下面这个动图为例，我们来看看 \(\textit{BFS}\) 是如何做的？
从上图可以看出，\(\textit{BFS}\) 的运行过程可以描述如下：
- 首先选择一个顶点作为起始结点，并将其染成蓝色，其余未访问结点为黑色；
- 将起始结点放入队列中；
- 从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部，将已访问过结点涂成蓝色，没访问过的结点是黑色。如果顶点的颜色是蓝色，表示已经发现并且放入了队列，如果顶点的颜色是黑色，表示还未访问；
- 按照同样的方法处理队列中的下一个结点，直到所有节点都访问完毕。
伪代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17procedure 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)可能就有直连的高速公路，这里不妨设距离为 \(300km\) 。
从 法兰克福(Frankfurt) 出发到 斯图加特(Stuttgart)，可以直达也可以经 卡塞尔(Kassel) 到 斯图加特(Stuttgart) 。假如 卡塞尔(Kassel) 到 斯图加特(Stuttgart) 只有 \(20km\) 的话，那么这条路线就是从 法兰克福(Frankfurt) 到 斯图加特(Stuttgart) 的最短路径。
为了减少后续书写时间，我们用 \(d_{F \to S}\) 来表示从 法兰克福(Frankfurt) 到 斯图加特(Stuttgart) 的距离。
但如果直接用 \(\textit{BFS}\) 算法去做的话，我们计算得到的 \(\min {d_{F \to S}} = 300km\) ，而不是
\[ d_{F \to S} = d_{F \to K} + d_{K \to S} = 173 + 20 = 193km \]
那么用 \(\textit{BFS}\) 求最短路径问题出在哪里呢？
我们可能会想到遍历顺序影响了答案，假如我们先遍历到 卡塞尔(Kassel)，然后就可以发现 \(\min {d_{F \to S}} = 193km\) 。但在 \(\textit{BFS}\) 中，我们会发现我们无法再去遍历 斯图加特(Stuttgart)，因为在遍历 法兰克福(Frankfurt) 时，斯图加特(Stuttgart) 作为 法兰克福(Frankfurt) 的邻居节点已经遍历了，所以我们无法再次遍历 斯图加特(Stuttgart)了！
\(\textit{BFS}\) 作为和 \(\textit{DFS}\)8 齐名的遍历算法，此时此刻束手无策了！
是的，时代变了， \(\textit{BFS}\) 你需要改变！
时代变了，拥抱变化的 BFS
回到 \(\textit{BFS}\) 的代码中，我们发现是下面这行代码阻止了我们再次访问 斯图加特(Stuttgart) ：1
2if w is not labeled as explored then
# visit neighbor
但是我们又需要记录每个节点的遍历状态，要不然程序会陷入死循环中。那么我们怎么才能再次遍历某个节点呢？
当…当…当…！
答案很简单，如果我们发现了一条更好的路径时，我们就可以再次访问这个节点。
我们使用一个数组 \(\textit{dist}\) 存储源节点到每个节点的距离，初始设置 \(\textit{dist[i]}\) 为无穷大，如果发现当前节点 \(\textit{cost}\) 更低时，就遍历该节点并更新 \(\textit{dist[i]}\) ，伪代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22procedure 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)
呼之欲出的 \(\textit{Dijkstra}\) 算法
用一个动画来描述上一章中优化的 \(\textit{BFS}\) 算法，如下图所示：
通过上面对 \(\textit{BFS}\) 的优化，我们已经很接近 \(\textit{Dijkstra}\) 算法了！如果我们我们把队列 \(Q\) 改成 \(\textit{PriorityQueue}\) 的话， \(PQ\) 存储的对象为 \([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
22procedure 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])
到这里，你有没有意识到，实际上我们已经重新发明了一遍 \(\textit{Dijkstra}\) 算法呢？
如果我们早生几十年，抢在 Edsger Wybe Dijkstra 9 老爷子在 1956 年之前先发表这个算法，也许这个算法的名字就冠于我们的名字了呢？:-D