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