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

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) 的最短路径

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

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

dFS=dFK+dKS=173+20=193kmd_{F \to S} = d_{F \to K} + d_{K \to S} = 173 + 20 = 193km

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

我们可能会想到遍历顺序影响了答案,假如我们先遍历到 卡塞尔(Kassel),然后就可以发现 mindFS=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 ↩︎