假设路线中的负边代表回赠:总长度为负的回路可以反复走,若之后仍可到达目的地,便没有最短游走。Bellman–Ford 方法能区分这种情况、有限的最短距离,以及根本不可达的目的地。
游走与递推式
定义 24.1.1
(游走与边数受限距离)
设有限有向图 有 个顶点,起点为 ,每条边的长度 均为有限实数。游走可以重复顶点和边;路径不重复顶点。游走长度是各次经过的边长之和。令 为从 到 、最多使用 条边的游走的最小长度;若不存在则定为 。令 为所有 到 游走长度的下确界;没有游走时定为 ,也可能为 。
空游走长度为零,因此 ,其余 。
命题 24.1.2
(边数受限的递推式)
对 ,约定 ,并把没有进入 的边时的内层最小值定为 ,有
证明
(按是否用上最后一条边分情况)
允许的游走要么最多使用 条边,要么恰用 条,最后一条为某个 。后者的前段最多使用 条边,长度至少为 ;反过来,在取得该最小值的前段后加上 ,便得到允许的游走。有限图中边数不超过 的游走只有有限多个,所以有限最小值确可取得。两种情况取最小值便得递推式。
每行必须由上一行计算,才有上述边数意义。原位更新也可用于通常的算法,但一轮内可能沿多条边传播,其中间结果未必等于这里的 。
概念视角代数
Bellman–Ford 即极小加算术中的矩阵幂
令 为由 到 的弧中最短的长度,若没有这样的弧则为 ,再把每个对角元素换成它与 的较小者。在以 作“加法”、以 作“乘法”的算术中,定义 。递推式恰好是 ,所以 ,而 的 元素就是至多 条弧的 到 游走的最短长度。
常见错误
(把原位更新的一轮当作 那一行)
在下面的表格例子中,按所列次序对各边做一轮原位更新:先得 、,再经 得 ,,再经 得 ,然后经 得 。仅一轮后 已是 ,但 :没有一条边的游走能到达 。最终标号仍然正确,但“最多 条边的游走”这类陈述只对同步计算的各行成立。
分辨三种距离
计算至 后,对每条满足 且尾点标号有限的边 ,标记其终点 ;再标记所有能从已标记点到达的顶点。
定理 24.1.3
(三类目的地的精确判别)
已标记顶点的距离为 。没有标记且 的顶点不可达。其余顶点的距离有限,等于 ,并由一条简单路径取得。因此可由起点到达的负回路,只有在它也能到达目的地时才影响该目的地。
证明
(改善暴露负回路,负回路迫使改善)
若某边能在第 行后改善终点,取一条取得其有限尾点标号的游走,接上该边,得到一条至多 边、比终点标号严格更短的游走。它必重复顶点,且分解出的回路至少一个为负;否则删去全部非负回路便得到不超过 边、长度不增的游走,产生矛盾。这负回路可从起点到达,也能通往被标记终点及其所有后继;反复走该回路,长度便趋向负无穷。
反之,取任何从 可达的负回路。其顶点均有有限的 标号,因为可达顶点有至多 边的简单路径。若回路上没有一条边可改善,将各式 沿回路相加,便得零不大于负的回路长度,矛盾。因此至少一个回路顶点被标记,并传播至其所有后继。未标记的可达目的地,其任何游走都不能经过负回路;删去非负回路后得到长度不增的简单路径。有限多条简单路径之中有最短者,且它至多使用 边,故其长度就是 。同理,可达顶点必有有限标号,所以无穷标号表示不可达。
证明透视
标记为何既不遗漏也不多报
证明包含三个独立论断。第 阶段后仍有改善,会给出至多 边的游走,于是某顶点重复,回路分解中必有负回路。可达负回路经伸缩求和必给出改善。未标记的可达目的地有有限距离,并由简单路径取得。
关键一步:若回路上没有边可改善,标号 在该回路上满足 ,即构成势,而势不能与负回路并存。可达性正是在这里用上:它令这些标号有限,求和才有意义。
缺了什么会出错:若改用非严格比较,零长度回路会被误报(第 4 道练习)。若省去传播一步,回路上的顶点可能被漏掉:在第二个表格例子中,边 给出 ,与 相等,所以 从来不是改善边的终点,但 。
如何收尾:阶段数上限 正是简单路径的边数上限;排除负回路后,之后不可能再出现更短的游走。
当 时仍适用:先用 ,额外扫描会发现负自回路。零长度回路可以重复,却不会令距离变为负无穷,也不会仅因可重复而触发严格改善。
完整算例
例题 24.1.4
(有负边但没有负回路)
取边 、、、、、、、。唯一有向回路 的长度是 。逐行由上一行计算:
| 最多边数 | |||||
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 0 | 4 | 5 | ||
| 2 | 0 | 4 | 2 | 8 | 9 |
| 3 | 0 | 4 | 2 | 5 | 6 |
| 4 | 0 | 4 | 2 | 5 | 6 |
例如 ,而 。第 4 行之后没有边可再改善。路径 的长度为 ; 也长 6,均取得已证实的最短距离。负边不妨碍 Bellman–Ford;Dijkstra 的标准证明则需要非负边长。
例题 24.1.5
(负回路与标记步骤)
现在只把 的长度由 改为 ,回路 的长度便是 。第 至 行不变。第 3 行给出 、 及 。第 4 行给出 、、,而 仍是 。
额外扫描找到两条改善边: 给出 , 给出 。所以 和 是被标记的终点。由 经 传播,标记 。因此 。重复回路不能反向通往 或 ;它们的距离仍为 4 和 0,也没有被标记,因为没有边从回路通向它们。
例题 24.1.6
(含负回路的不可达分量)
取顶点 及边 、、,故 。回路 的长度为 ,但没有边由 进入 。从 起,每行对 都是 。
额外扫描中,回路上的边尾点标号为 ,因而被排除,没有任何标记。定理于是把 判为有限距离 ,把 判为不可达。负回路存在,却与从 出发的每个距离无关;正是尾点标号有限这个条件,令它不被误报。
反例模式
负边不等于负回路
一个看似合理的说法是:有负边便令距离无界。若图中只有长度 的边 ,则 、。额外扫描比较 与 ,没有严格改善,没有标记,距离是有限的 ;单一负边不能重复走。反过来,可达负回路若不能到达 ,也不会令到 的距离变为负无穷,正如第 2 道练习所示。判别定理所需的是:可达、且能到达目的地的负回路。
常见错误
(只标记改善边的终点)
额外扫描只找到改善边的终点。位于回路上或其后的顶点,即使不是这种终点,距离也可能是 ,正如第二个表格例子中的 。报告有限距离之前,必须沿所有边传播标记。
还原路径与运算量
对有限、未标记的目的地,可在每个状态 记录其值承继自上一行,还是由某条进边取得。由 向前追踪,每次减少 ;把记录的边倒序便得到取得最小值的游走。删去重复顶点形成的回路:对未标记目的地它们均非负,若删掉正回路会与最优性矛盾,所以可得到最短简单路径。相同标号可任选一个来源。每点只存一个前驱而不小心处理更新,并不等同记录每个阶段的选择。
以邻接表计算,初始化与 次同步扫描连同复制各行需 时间;标记及可达搜索需 。两行距离只需 空间;直接保存各阶段还原选择需 。这是算术运算次数,实际位复杂度取决于边长的表示。额外扫描有改善表示存在可达负回路,并不表示每个目的地都受影响。
练习
快速检查
(已知 、、,求距离并解释为何没有负回路。)
解答 · 答案
经 的路长 ,小于直接路线的 0,故答案为 。所有边均向前,没有有向回路。
快速检查
(已知 、、,没有其他边。分类 。)
解答 · 答案
的距离为 0;反复自回路令 的距离为 ; 的距离为 3,因回路不能到达 。
快速检查
(,边为 、、。求 ,指出额外扫描中可改善的边。)
解答 · 答案
同步计算得 、,以及 、。边 给出 ,标记 ,再传播至 。
快速检查
(为何把严格改善换成非严格比较会错判零回路?举例。)
解答 · 答案
起点有一条零长度自回路时,;等号并非改善,所有游走长度均为零,距离有限。