最短路径:从 BFS 到 Dijkstra 和 Bellman–Ford¶
先修:图的表示、按离起点的步数一圈圈访问(广度优先遍历,BFS)、堆。
读完能做:把连线上标的时间或代价记为**边权**。读完后,能按边权选择找路的算法,并手算一次「找到更省的走法时,怎样更新已记下的距离」(松弛)。Dijkstra 和 Bellman–Ford 是这一页要学的两种做法。
同一张图,两种“近”¶
从 S 到 T,有一条直接边,代价 9;也可以走 S → A → T,两条边的代价分别是 2 和 3。按跳数(经过的边数),直接走只需一跳;按代价,绕路只需 5。BFS 把每条边当作同样的步长。边权不同时,要记录的是目前发现的**最小总成本**。
给每个点保存一个暂定距离。起点为 0,其余为无穷大。考察边 u → v 时,比较「已知到 v 的距离」和「先到 u,再走这条边的距离」。后者更小就更新距离,并把 u 记为 v 的**前驱**,也就是新路线到达 v 前的上一站。这一步叫**松弛**。记前驱便能从终点倒着恢复路径。
「暂定」的意思是目前已经找到一条这么便宜的路,之后还可能找到更便宜的路。无穷大表示还不知道怎么到那里。比如第一次直接走 S → T 得到 9,暂记 T = 9,前驱是 S;沿 A 走到 T 后算出 2 + 3 = 5,改成 T = 5,前驱是 A。最后从 T 按前驱倒走得到 T、A、S,反过来才是实际路线 S → A → T。
Dijkstra 如何确定一个点¶
如果每走一条边的代价都大于或等于 0(边权非负),可以反复从未确定的点中取暂定距离最小的一点,再检查从该点出发的每条边(出边)能否让邻居的暂定距离变小。任何先绕到其他尚未确定点的路线,已经付出的代价至少和当前最小距离相同,之后的边代价还会继续累加。所以取出的距离可以确定下来。
| 操作 | A 的暂定距离 | T 的暂定距离 |
|---|---|---|
| 从 S 出发,松弛两条出边 | 2 | 9 |
| 取出 A,再松弛 A → T | 已确定为 2 | 5 |
| 取出 T | 2 | 已确定为 5 |
为什么 T 的 9 还不能确定,A 的 2 却可以? 打开 S 后,两个候选里 A 最便宜。假设还有一条更便宜的路能到 A,沿这条路从 S 走,必然有第一个还未确定的点。它的上一点已经确定,那条边早就放进比较了。由于后面再走的边都不会让成本降低,这个点也一定比当前的 2 更便宜,和「A 已是候选里的最小值」矛盾。这个思路是把「当前能找到的最小」变成「可以确定的最小」的关键。
每一步都要取出暂定距离最小的候选,可以用最小堆保存 (距离, 节点)。例如 T 的距离从 9 改成 5,把 (5, T) 再加入堆,旧的 (9, T) 可以留在里面。以后取到旧条目时,和距离表上的 5 一比较就知道要跳过。对邻接表和二叉堆,这种实现的时间上界可写成 \(O(V+E\log(E+2))\),其中 \(V\) 是点数,\(E\) 是边数。
负权为何改变算法¶
把 S → T 改为 2,S → A 改为 5,A → T 改为 −8。T 会先以距离 2 出队,但经 A 的真实成本是 −3。Bellman–Ford 的做法是反复扫描所有边。想象再加一条 T → A,代价 1。沿 A → T → A 绕一圈的总成本是 −7,这种绕回来还省了代价的环叫**负环**。若从起点能到达这个环,就能在去往环后面各点的路上再绕一圈,让成本一再下降。若没有可达负环,可以删掉路线中的非负代价环,找到一条同样便宜且不重复经过节点的**简单路径**。一张有 \(V\) 个点的图中,这样一条路最多有 \(V-1\) 条边。每扫完一轮,至少能把正确的候选距离沿路线再推进一条边,所以 \(V-1\) 轮足以处理这些路径。再扫一轮仍能降低某个可达距离,说明有可从起点到达的负环。时间复杂度为 \(O(VE)\)。
| 情况 | 先选 |
|---|---|
| 所有边等权,只关心走几步 | BFS |
| 所有边权非负 | Dijkstra |
| 边权可负,需要检查可达负环 | Bellman–Ford |
路由协议还要考虑每台设备拥有什么信息,以及链路变化后,设备要多久才能重新得出稳定的转发规则(收敛)。可以接着读转发与路由。
自测¶
把 A → T 的代价从 3 改为 7。S 到 T 的最小成本是多少?哪种做法能保留两条同成本路径?
参考思路
两条路线的成本都是 9。标准松弛记录一个前驱即可返回一条最短路,也可以在候选成本相同且已知有限时收集多个前驱。零权边可能使这个前驱关系含环,枚举路径时还需定义是否允许重复节点。