1. 背景与约定
定义 16.1.1
(途径与最短距离)
设 为有限有向图,其中 ,,实数权重 ,源点 (因此 )。途径(walk)可以重复经过顶点和边。允许在 处取零条边的途径,其权重为 。
最短距离定义为所有途径权重的下确界:
其中 。
计算约定。
- 我们采用实数 RAM 模型,其中实数的加法和比较代价为 。
- 是一个哨兵值。对实数 ,它满足 且 。
- 由于权重均为实数,表达式 永远不会出现。算法从不存储 ;该标记是事后根据可达性赋予的。
- 边列表可在 时间内枚举所有边。常规的邻接表遍历还需扫描所有顶点,代价为 。
2. 有界长度距离与递推式
定义 16.1.2
(有界长度距离)
定义 为从 到 的、至多含 条边的途径的最小权重;若不存在这样的途径,则为 。对固定的 ,这样的途径只有有限多条,因此最小值存在。
命题 16.1.3
(有界长度递推式)
数值 满足 ,且对 有 ;并且对每个 :
证明
(d_i 与右端之间的两个不等式)
记右端为 。我们分别证明两个方向的不等式。
- ()至多含 条边的途径也至多含 条边。此外,一条至多含 条边、到达 的途径,后接边 ,便是一条至多含 条边、到达 的途径。因此 中的每个候选值都是 所考虑的某条途径的权重。若某一项为 ,则不等式平凡成立。
- ()取 的一条最优途径 。若 至多含 条边,则 。否则 恰含 条边,故其最后一条边为某条 。其前缀含 条边,故 。若不存在途径,则两端均为 。
同步 Bellman–Ford 利用两个数组由 计算 。每一轮扫描所有边,并且只读取旧数组。原地更新(异步变体)同样正确,但其中间值不再恰好等于 。这正是我们分析同步版本的原因。
概念视角结构
把各轮看成无圈图的分层
为每个顶点作副本 。每条边都把 连到 ,权重为 ;另把 连到 ,权重为 。这个分层图没有圈,而 就是从 到 的路径的最小权重。 中的负环,在分层图里就成为一条沿各层不断下降的路径。
3. 轮之后的有限距离
若一个环包含某个顶点 ,满足 且 ,则称该环与 相关。
引理 16.1.4
(n−1 轮后的有限距离)
若 可达,且不存在与 相关的负环,则 ,且该值有限。
证明
(删去非负的闭子途径)
– 途径上的每个顶点都从 可达,且都能到达 。因此,这样一条途径的任一闭子途径 都可分解为若干与 相关的简单环。这些环的权重均非负,故 。于是删去 绝不会使权重增加。反复进行这一操作,便得到一条至多含 条边、权重不超过原途径的简单路径。因此每条途径的权重至少为 ,从而 。反向不等式 由定义即得。
引理 16.1.5
(相关负环迫使距离为负无穷)
若存在与 相关的负环 ,则 。
证明
(反复绕环)
从 走到 上的某个顶点 ,沿 绕 圈,再从 走到 。其权重为 ,当 时趋于 。
推论 16.1.6
(距离的三分性)
两个引理合起来给出一个三分法:
- 当且仅当 不可达;
- 当且仅当存在与 相关的负环;
- 其余情况下 。
4. 额外一轮所证明的内容
再多计算一轮 ,并令 。
命题 16.1.7
(额外一轮所证明的事实)
设 。(i) 若 ,则存在可由 到达的负环。(ii) 若存在可由 到达的负环,则每个这样的负环都含有 中的顶点。(iii) 每个 都有 。
证明
(三项结论的证明)
(i) 存在从源点可达的负环。
假设不存在可达的负环。由有限距离引理,在可达顶点上 。由于 ,第 轮不会改变任何值。不可达顶点保持为 。
(ii) 存在从源点可达的负环 。
设 为这样一个环。每个 均可达,故 有限。用反证法,假设对每个 都有 。由递推式得
沿 求和得 ,矛盾。事实上这证明了更强的结论:每一个可达负环都包含 中的某个顶点。
(iii) 。
若 有限,则有限距离引理 的证明表明每条 – 途径的权重至少为 。特别地,,这与 矛盾。
证明透视
为什么绕环求和必定闭合
唯一不显然的一步是 (ii)。假设 上没有顶点在第 轮改变,就可以把递推式(关于 的不等式)读成同一个数组 的两个值之间的不等式。沿 把这些不等式相加,所有标签互相抵消,只剩下 。这次抵消用到可达性:所有 都是有限值,减法才合法;若标签是 ,就什么也抵消不了。论证是对整个环作反证,所以只证明 上有某个顶点改变,并不能指出是哪一个。(i) 则从另一个方向收尾:若没有可达的负环,有限距离引理 已使 在可达顶点上等于 ,第 轮就没有可改进之处。
额外一轮不能说明的内容。
- 中的顶点不一定位于某个环上。
- 不在 中的顶点仍可能有 ,因为它可能只是恰好在这一轮中没有得到改进。
反例模式
X 并不等于负无穷顶点的集合
声称: 恰好当 。取顶点 与边 (1)、()、(1)、(0),故 。环 的权重为 。依次列出 ,由递推式得 、,所以 。然而 在环上,故 ; 可由该环到达,故 。因此 (iii) 的逆命题不成立: 只记录在这一轮有所改进的顶点。正确的陈述是下面的定理 ,在此例中等于 。
定理 16.1.8
(负无穷顶点就是可由 X 到达的顶点)
,即在 中从 的某个顶点可达的所有顶点构成的集合,包括 本身。
证明
(两个包含方向)
我们分别证明两个方向的包含关系。
- ()由 (iii), 中每个顶点都有 。此外, 且 蕴含 。因此该标记沿边传播到整个 。
- ()若 ,由有限距离引理(逆否命题)可得一个与 相关的负环 ,满足 。由 (ii), 包含某个 。于是 沿 可到达 ,而 可到达 ,故 。
最终输出。 从 出发运行 BFS 或 DFS,并输出:
- 在 上输出 ;
- 在 处输出 ;
- 其余情况输出 。
这几种情况互不相交。 中的每个顶点都是可达的,从 可达的每个顶点也都是可达的。
两点区分。
- 从 不可达的负环不会影响任何距离,额外一轮也无法察觉它。其顶点保持为 。
- 从 可达、但从任何源点可达的负环都不可达的顶点保留有限值 。
例题 16.1.9
(哪些顶点的距离是负无穷)
例如,取边 (权重 1)、(权重 1)、(权重 )、(权重 1),外加一个独立的环 ,其总权重为 。那么:
- ;
- ;
- 。
5. 例题详解
例题 16.1.10
(含一条负边的图上的五轮计算)
顶点为 ,。边如下:
| 边 | |||||||
|---|---|---|---|---|---|---|---|
| 权重 | 1 | 3 | 3 | 1 | 5 | 2 |
共有两个简单有向环:,权重为 ;以及 ,权重为 。两者均非负,因此不存在负环。
| 轮次 | |||||
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 1 | 0 | 1 | 3 | ||
| 2 | 0 | 0 | 3 | 4 | 8 |
| 3 | 0 | 0 | 3 | 3 | 5 |
| 4 | 0 | 0 | 3 | 3 | 4 |
| 5(额外) | 0 | 0 | 3 | 3 | 4 |
该表可直接由递推式得出。有三个条目值得核对:
- 第 2 轮中,。
- 第 4 轮中,,这用到了四条边的路径 。
- 第 5 轮中,。
全部 轮确实都是必需的。额外一轮没有改变任何值,因此 ,与不存在负环相一致。
例题 16.1.11
(只有一个顶点与一条自环)
设 ,只有一条权重为 的自环 。此时 ,普通轮数 ,并且 。额外一轮计算 。若 ,则 ,所以 且 :这条自环是非负环。若 ,则 ,所以 且 ,因为绕自环 次的权重为 。即使是最小的图,也要靠额外一轮才能发现它的负环。
反例模式
过早定型一个顶点
声称:上面的图没有负环,所以标准的 Dijkstra 能算出正确的距离。
Dijkstra 算法的正确性论证需要非负权重。在这一假设下,离开已定型集合的路径以后绝不可能变得更便宜。下面是教科书式 Dijkstra 在此图上的运行过程,其中顶点在被取出时即被定型:
- 取出 。令 ,。
- 以 1 取出 并将其定型。令 。
- 以 3 取出 。边 本可将 降至 ,但 已被定型。令 。
- 以 4 取出 。令 。
- 取出 。
输出为 、、。真实值分别为 、 和 。
若某个变体确实将 降至 ,但从不重新扫描 的出边,则 仍为 。负权边破坏了该算法所依赖的不变量。
补救办法是只在权重非负时使用 Dijkstra;有负边时改用上述有界长度的轮次,它在第 轮之前不会定型任何顶点。
6. 复杂度
命题 16.1.12
(含额外一轮的 Bellman–Ford 开销)
含额外一轮及从 出发的最后搜索的同步 Bellman–Ford,时间为 ,空间为 。
证明
(计算轮数、边数与存储空间)
- 轮数。 算法运行 轮: 个普通轮加上额外的一轮。
- 每轮代价。 每轮扫描 条边,并复制一个长度为 的数组,代价为 。总代价为 。
- 常见的 界。 首先在 时间内求出从源点可达的子图;记 为其顶点数与边数。若 ,则 ,因此各轮耗时 。计入最初的搜索,总计 。若 ,则各轮耗时为 ,这包括无边的情形以及可能存在自环的情形。
- 从 出发的可达性。 代价为 。
- 空间。 足以容纳图、两个距离数组以及搜索所需空间。
表示方式的注意事项。 直接枚举边的代价为 ,另加 的数组初始化或复制。使用常规邻接表时,扫描顶点及其边每轮同样为 。若图以邻接矩阵给出,则每轮扫描代价为 , 轮共计 。
7. 常见错误
常见错误
(有负环时把 当作答案)
上面反例中的顶点 有 ,是完全有限的值,但 。 只对没有相关负环的顶点才是距离;额外一轮和从 出发的搜索正是用来处理其余顶点的。
常见错误
(把源点到不了的负环也算进去)
若从 没有任何途径通向某个负环,它不会改变任何 ,其所有顶点在每一轮中的标签都保持为 。“整个图中存在负环”是另一个问题;本算法回答的是从 出发的途径的问题。
常见错误
(用有限的哨兵值代表无穷)
若把 存成一个很大的有限数 ,则从未到达的顶点沿权重为 的边松弛会得到 ,看起来比 更好。于是未到达的顶点会出现在 中,或得到虚假的有限标签。使用 前应先确认它是有限值,或使用满足 的真正无穷。
8. 练习
快速检查
(在五轮例题的图中,只做 轮能否读出 ?写出 与 。)
看看通往 的最佳路径含有多少条边。
解答 · 答案
不能。表中 ,但 ,由四条边的路径 取得,并于 才首次出现。含 条边的最短路径需要 轮。
快速检查
(顶点 (故 ),边 (2)、()、(1)、(4)。求 及每个 。)
先算 与 ,再用 。
解答 · 答案
环 的权重为 。对 ,各轮给出 、,所以 。于是 ,即 ,而 。注意 与 是不在 内的负无穷顶点。
快速检查
(某图有一个源点 到不了的负环。该环上的 是多少?它为 贡献哪些顶点?)
哪些标签有可能变成有限值?
解答 · 答案
该环上每个顶点的 ,因为没有从 到它的途径。它们的标签在每一轮都保持 ,所以没有任何一个属于 。算法看不见这个负环,这正是正确的。
练习 16.1.13
(证明:若 在每个顶点上成立,则对所有 都有 。)
核心证明
解答(3)
- 1
把递推式写成映射
令 把数组 送到数组 。则对每个 都有 。
- 2
对 k 作归纳
关键一步
时结论显然成立,而 就是假设。若对某个 有 ,则 。
依据: 每个数组只由前一个数组决定。
- 3
得出结论
∎所以对所有 都有 ,再多做任何一轮也不会改变任何标签。