贝尔曼-福特算法
有些最短路径问题中,有的边会让路径更便宜:一笔退款、一段下坡路、一个对你有利的汇率。Dijkstra 算法应付不了它们。Bellman–Ford 算法可以,它用耐心换掉了巧妙。
思路
每种最短路径算法都依赖同一个操作:松弛一条边。如果先到 u 再沿边 u → v 走比已知到 v 的最佳路线更短,就采用它。Dijkstra 算法把每条边松弛一次,所用的巧妙顺序只在没有负权边时才有效。Bellman–Ford 不做这种假设。它按任意固定顺序一遍又一遍地松弛每条边,直到距离不再变化。
分步说明
把起点的距离设为 0,其他节点设为无穷大。对 n 个节点,重复 n − 1 次:遍历每条边 u → v,如果 u 有距离就松弛它。如果整整一趟没有任何改变,就提前停止。然后再进行一趟。如果仍有边能松弛,说明从起点能到达一个总长为负的环;否则每个距离都是最短的,记下的节点给出路径。
一个例子
取单向边 A → B 长度为 4,A → C 为 5,B → D 为 2,C → B 为 −3,按此顺序检查,从 A 开始。第 1 趟给出 B 4、C 5 和 D 6,然后 C → B 把 B 降为 5 − 3 = 2。第 2 趟把 D 降为 2 + 2 = 4。第 3 趟没有改变,所以答案是 B 2、C 5、D 4。Dijkstra 算法会在看到负权边之前就把 B 确定为 4、D 确定为 6。再加一条长度为 −4 的边 D → C,环 C → B → D → C 的总长为 −5:每一趟都会再次降低距离,检查趟会报告它。
为什么 n − 1 趟就够
最短路径(如果存在)从不重复经过节点,所以最多有 n − 1 条边。无论边的顺序如何,一趟松弛所有边都会把每条已正确知道的最短路径再延长一条边。所以第 k 趟之后,所有最多 k 条边的最短路径都是正确的,n − 1 趟之后就全部正确。顺序仍影响速度:好的顺序可能一两趟就完成。
历史和应用
Alfonso Shimbel 于 1955 年描述了这个方法,Lester Ford Jr. 于 1956 年、Edward F. Moore 于 1957 年、Richard Bellman 于 1958 年也分别描述了它;它以其中的 Bellman 和 Ford 命名。它的每一趟可以由每台路由器独立运行,因此成为 RIP 等距离矢量路由协议的基础。在金融中,对汇率取负对数,就能把一轮有利可图的货币兑换(套利)变成一个负环,Bellman–Ford 可以找到它。
动手探索
打开应用,按“单步”。每条边都是单向的,有些长度为负。每一步按固定顺序检查一条边,图块显示当前趟数以及这一趟改变了多少个距离。通常很快就有一趟没有任何改变,搜索提前停止。勾选“加入负环”,观察距离一趟接一趟地下降,直到检查趟找到这个环并把它画成红色。
常见问题
Bellman–Ford 算法的时间复杂度是多少?
对 V 个节点和 E 条边为 O(V · E):最多 V − 1 趟,每趟检查每条边。有了提前停止,实践中往往快得多,最好情况下一趟就够。
什么是负环?
边长加起来小于零的环。反复绕它走,可以让路径要多短有多短,所以经由它能到达的每个节点都没有确定的最短距离。
Bellman–Ford 算法适用于无向图吗?
只有在没有负权边时才适用:一条无向的负权边可以来回穿过,这本身就是由两条边构成的负环。边都非负时它能用,但 Dijkstra 算法更快。
什么是 SPFA?
最短路径快速算法(Shortest Path Faster Algorithm),Bellman–Ford 的一个变体,用队列只重新检查距离刚改变的节点的出边。它通常快得多,但最坏情况相同。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试贝尔曼-福特算法