Dijkstra 算法
你的导航应用知道从你家门口到几乎任何地方的最快路线。这一想法的核心,是 Edsger Dijkstra 在 1956 年用大约二十分钟想出的一个算法:从起点向外扩展,总是先完成最近的地方。
基本思想
想象一些城镇由长短不一的道路相连。问题是:从我的城镇到其他每个城镇的最短路线是什么?如果每条路都算作一样,广度优先搜索就能回答;但在这里,经过更多道路的路线可能反而更短。Dijkstra 算法为每个城镇记录目前找到的最短距离,并扩展一片距离已确定的城镇区域,每次加入尚未确定的最近城镇。
分步说明
起点的距离设为 0,其他每个节点设为无穷大。把起点放入优先队列,这种队列总是交出距离最小的节点。取出这个节点,它的距离现已确定。对每个尚未确定的邻居,算出经过这个节点的距离:它的距离加上边的长度。如果这比邻居目前的距离短,就把邻居的距离降低,记下这个节点作为通往那里的路线,并把邻居放入队列。这叫作松弛一条边。重复,直到队列为空,或终点被取出。
示例
取边 A–B 长 4、A–C 长 1、B–C 长 2、B–D 长 1、C–D 长 5、D–E 长 3,从 A 出发。取出 A 后,B 的距离为 4,C 的距离为 1。C 最近,于是以 1 确定;经由 C,B 降为 1 + 2 = 3,D 得到 1 + 5 = 6。现在 B 最近,以 3 确定;经由 B,D 降为 3 + 1 = 4。D 以 4 确定,E 得到 4 + 3 = 7。所以从 A 到 E 的最短路线是 A → C → B → D → E,长度 7,尽管 A → B → D → E 用的边更少,长度却是 8。
为什么它是正确的
假设节点 X 是队列中最近的节点,距离为 d。从起点到 X 的任何其他路线都必须在某处离开已确定节点的区域,而它在该区域外到达的第一个节点就在队列中,所以已至少相距 d。剩下的路程不会让它变短,因为没有负权边。所以 d 就是到 X 的最短距离。有负权边时,这一论证就不成立;这时改用 Bellman–Ford 算法,它会一遍又一遍地松弛每条边。
历史与应用
Edsger W. Dijkstra 在 1956 年设计了这个算法,通过寻找荷兰城市之间的路线来展示一台新计算机——阿姆斯特丹的 ARMAC,并于 1959 年发表。同样的思想配上更聪明的队列,运行在导航应用中,也运行在 OSPF 和 IS-IS 等互联网路由协议中,它们计算数据在路由器之间传输的最短路线。A* 搜索加上对剩余距离的估计,因此能朝终点前进,查看更少的节点。
动手探索
打开应用并按“单步”。边上的数字是边的长度,每个节点上的数字是它目前的距离。队列中的节点是蓝色,已确定的节点是绿色,图下方的队列按由近到远列出它们及其距离。留意距离下降的时刻:看起来更长的路线原来更短。再选一个终点,看搜索在终点确定时立即停止。
常见问题
Dijkstra 算法的时间复杂度是多少?
取决于优先队列。用简单列表时,对 V 个节点为 O(V²);用二叉堆时,对 E 条边为 O((V + E) log V);用斐波那契堆时为 O(E + V log V),这是 Michael Fredman 和 Robert Tarjan 在 1984 年证明的。
Dijkstra 算法能处理负权边吗?
不能。它假定节点一旦成为队列中最近的节点,其距离就不会再改进,而负权边可能打破这一点。对有负权边的图,请使用 Bellman–Ford 算法。
Dijkstra 算法会求出到每个节点的路径吗?
会。运行到结束时,它给出从起点到每个可到达节点的最短距离,记下的节点构成一棵最短路径树。如果只需要一条路径,在终点确定时提前停止可以省去工作。
Dijkstra 算法和 A* 有什么关系?
A* 搜索就是带提示的 Dijkstra 算法:它按目前的距离加上剩余距离的估计值(比如地图上的直线距离)来排列队列。估计得好,它就能找到同样的最短路径,而查看的节点少得多。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试 Dijkstra 算法