负权边可能带来较短路线
假设边的权重记录成本变化,其中包括返还或退款。负权边可以有实际意义,却也改变了最短路径算法必须证明的事情。当前看似昂贵的路线,可能在之后经过负权边,改善某个看似已确定的距离。Dijkstra 算法所用的贪心定案步骤,就失去原有依据。
Bellman–Ford 依靠另一种推进方式:允许路线使用更多边,并把已知路线延长一条边,反复改善距离估计。关键问题是:最优解存在时,为什么有限轮次就足够?如果之后仍能改善,又能推知什么?
本节由动态规划及不变量分析出发,发展最短路径算法。我们会分清两种计算:递推表格的轮次有明确含义;原地更新实现的一轮,却可能已沿多条边传播改善。
规定图问题与例外情况
设 是有限有向图,,源点为 ,每条边有实权重 。平行边可保留为不同的边记录,也允许自环。数学分析中的运算及比较都为精确。
游走是端点相接的有向边序列,可以重复顶点或边,其权重为所经各边权重之和。从 到自己的空游走,权重为零。简单路径不重复顶点,因此至多有 条边。
定义 7.1.1
(最短游走距离)
对 ,以 表示全部从 到 的游走权重之下确界,有三种可能:
- :从 不能到达 ;
- 有限最小值:存在一条最优游走;
- :到 的游走权重可以任意小。
负环是总权重为负的有向环。如果从 可到达某负环,而且从该环可到达 ,就可先反复绕环再前往 ,证明 。
可达条件不可省略。图中另一部分的负环,不影响从 出发的路线。即使负环可达,也不是每个顶点的距离都变成 :只有从该环能到达的顶点才受影响。下方算法报告的是:是否有某个负环可从 到达;它本身不会把所有距离为 的顶点分类。
先限制游走的边数
对整数 ,定义 为从 到 、使用至多 条边的游走之最小权重;如果没有这种游走则设为 。固定有限的 后,这类游走只有有限多条,所以即使图有负环,有限最小值仍存在。
初始值为
至多使用 条边的游走,要么本来已使用至多 条,要么最后一条边是 ,之前至多有 条边。因此
如果前一个值为 ,就跳过该候选。没有任何入边候选时,内层最小值设为 。保留第一项十分重要:边数是“至多”,不是“恰好”。
命题 7.1.2
(边数上限递推式)
对每个 及每个 ,上面定义的 都满足该递推式,而右边只需由第 行计算。
证明
(按最后一条边分解)
设 为右边的值。至多使用 条边的游走,要么至多使用 条边,其权重至少为 ;要么以某条 结束,之前的起始部分至多有 条边。起始部分的权重至少为 ,所以整条游走的权重至少为候选值 。因此 ;如果 ,就没有合规游走。
反过来, 的每个有限项都是某条合规游走的权重: 由至多 条边的游走取得,有限候选则由一条至多用 条边到 的最优游走接上 取得。因此 ,两者相等;由所规定的第 行出发,对 归纳,就证明整张表正确。
完整表格说明为什么需要多轮
使用顶点 ,边如下;除此以外没有其他边。
| 边 | 权重 | 边 | 权重 |
|---|---|---|---|
例题 7.1.3
(到 t 的最佳路线使用四条边)
每一行只能用前一行计算:
| 边数上限 | |||||
|---|---|---|---|---|---|
例如 。在边数上限二的一行,从 延长路线时尚不能使用新值 2,因为每一格都只能读取第一行,所以 。上限三才得到 及 ;上限四最后得到 ,由以下路径取得:
如果同一行内使用刚写入的值,计算描述的是原地扫描,而非这张边数表。这仍可能形成正确算法,但该行就不再具有所规定的精确含义。
没有可达负环时,为什么 n − 1 轮足够
定理 7.1.4
(没有可达负环时边数已经足够)
若从 不能到达任何负环,则对每个 都有 。
证明
(缩短重复顶点的游走)
假设从 不能到达任何负环。如果从 出发的游走重复某个顶点,两次出现之间构成闭游走。它可分解为有向环;按假设,每个环的权重均非负。移除这一段不会增加总权重。反复移除,直到没有重复顶点。
因此,每个可达的 都存在最优简单路径。简单路径只有有限多条,每条至多有 条边,所以对每个 都有
不可达顶点的两边均为 。对 ,空路径仍以零权重最优。此论证不要求每条边非负,而是要求不存在可达的负环。
用适当不变量证明原地松弛
一条边的松弛,是尝试候选值 d[u] + w(u,v),只有它较小时才取代 d[v]。一般实现只存储一个距离数组,反复扫描全部边。
BELLMAN_FORD(V, E, s):
d[v] = INFINITY for every vertex v
d[s] = 0
repeat n - 1 times:
changed = false
for each edge (u, v, weight) in E:
if d[u] is not INFINITY and d[u] + weight < d[v]:
d[v] = d[u] + weight
changed = true
if not changed:
return (d, no reachable negative cycle)
for each edge (u, v, weight) in E:
if d[u] is not INFINITY and d[u] + weight < d[v]:
return (no distance answer, reachable negative cycle)
return (d, no reachable negative cycle)
INFINITY 表示独立的不可达状态,不是可以放心加上权重的最大整数。固定宽度整数实现必须先检查此状态,并确保每个有限和都能由所选类型表示。本节证明使用精确运算;浮点数的舍入可能改变严格比较的结果。
与表格不同,原地扫描可以立即使用刚改善的值。如果按一条路径的前进方向扫描,一轮就可能把改善传到终点。我们不声称其标签等于相应的 行。
定理 7.1.5
(原地算法的精确性)
若从 不能到达任何负环,则算法返回时(经 轮,或在较早一轮没有任何改动时)所持有的标签 d[v],对每个 都等于 ;不可达的 则为 。
证明
(用两个不等式夹出原地算法的答案)
第一,每个有限标签 d[v] 都是某条从 到 的实际游走之权重。初始的零标签符合此性质;松弛时,把取得 d[u] 的游走接上该边,就保持此性质。因此没有可达负环时,。
第二,完成 次整轮边扫描后,。尚未扫描时成立。在下一轮中,标签只会下降,所以处理 时,当时的 d[u] 不大于该轮开始时的值,而归纳假设使后者不大于 。全部边处理完毕后,每个最后一条边的候选及原有标签都已考虑,递推式因此给出 。
没有可达负环时,完成 轮后,
所以标签精确。不可达顶点不可能取得有限标签,因为每个有限标签都有实际游走作证。即使存在负环,第二个不等式仍有用;需要小心的是第一个不等式所用的有限最优值解释。
证明透视
两个不同事实夹出答案
证明是一个夹逼,两边用到不同的事实。下界 只来自实际作证的游走,对环没有任何假设。上界 来自标签只会下降,所以原地扫描即使不能逐行重现边数表,也至少做得一样好。两边靠前面的等式 相接,而“没有可达负环”的假设正是在此处进入。
不明显的一步是与边数表比较,而不是分析扫描顺序,所以边的顺序完全无关。缺少该假设时夹逼就松开: 可以是 ,而 却是有限数,标签就不能被确认。下面的检测扫描处理这种情形。
如果整轮没有任何改动,每条松弛不等式就已成立。下一轮从同一组标签开始,会做完全相同的事,也不会改动。因此提早停止与继续扫描的结果相同。它也不会掩盖可达负环,下一个论证会说明原因。
例题 7.1.6
(提前停止的一次原地运行)
在五顶点图上运行算法,按表中的边顺序扫描:、、、、、、、。对 ,初始为 。
第一轮中, 令 , 令 。接着 给出 ,故 。然后 令 ,而 提供 ,并不更小。再由 令 , 提供 , 提供 。一轮后 ,已等于第 行。
第二轮中每个候选都不小于当前标签: 提供 , 提供 , 提供 。没有任何改动,所以算法在至多 轮中只做了两轮就返回。第一轮把改善传过四条边,因为边的顺序跟随路径;边数表的一行做不到这一点。
额外一次改善可检测可达负环
完成 轮后,再检查每条边一次,但不改标签。如果有限的 d[u] 仍能改善 d[v],就报告有可达负环;不要把当前数值当作最短距离返回。
定理 7.1.7
(负环检测)
设主循环已结束,不论是经 轮,还是在某一轮没有任何改动时。则存在边 ,其 d[u] 有限且满足 ,当且仅当从 可到达某个负环。特别地,有可达负环时不会出现整轮不变。
证明
(精确标签与沿环求和)
如果没有可达负环,前面的定理已使标签精确。把到 的最优游走接上 ,得到一条到 的可行游走,所以 ,任何边都不能严格改善终点。因此一旦发现改善,原假设就不成立。
反过来,假设有可达负环。从 到环上每个顶点都有一条简单路径,因此经 轮后,其标签均有限。如果环上没有任何边可松弛,每条边均满足 。沿环相加,所有距离标签抵消,得到 ,与负权重矛盾。因此至少一条边仍可松弛。
同样的求和也排除“有可达负环却出现整轮不变”:所有松弛不等式保持不变,会沿路径把从 出发的有限可达性传下去,之后就与负环矛盾。
证明透视
两个方向,两种引擎
两个方向并不对称。“没有环,所以没有改善”依靠标签的精确性,也就是依靠前面整个定理;它只多用到“延长游走仍得游走”这一点。“有环,所以有改善”除了环上标签有限之外,完全没有用到算法的任何性质。
后者的关键一步是抵消:如果环上每条边都满足松弛不等式,沿环相加时每个标签都以正负号各出现一次,留下 。逐条边成立的条件,经不起负的总和。有限性来自至多 条边的简单路径,这就是 轮足够的原因。如果环不可达,其标签保持 ,有限前驱检查会跳过其边,求和就无从形成;这就是不可达的负环不会被报告的原因。
例题 7.1.8
(负环影响部分距离,不是全部距离)
在五顶点图中加上权重为 的 。环 的权重为 ,从 可达,且环上顶点可到达 。因此 的距离均为 。由于没有边返回 ,源点的距离仍是零。检测报告有可达负环,但不会把每个项目改成 。
另一情况是保留原图不变,新增一个分离分量,包含权重为 的 及权重为 的 。这个环为负,但从 不可达。两个标签保持 ,有限前驱检查会跳过这些边候选。原分量的距离仍与完整表格相同。
负权边使 Dijkstra 的贪心证明失效
反例模式
已定案的距离之后仍可能需要改善
取顶点 ,只有以下边: 权重为 , 为 , 为 , 为 , 为 。
永久确定最小暂定标签的 Dijkstra 实现,会先把 以 2 定案,再把 以 4 定案,之后才处理标签为 5 的 。但 的权重为 。这个图根本没有有向环,因此问题来自负权边,不是负环。允许已定案顶点重新开启,会改变算法,通常的 Dijkstra 正确性与时间分析就不能直接沿用。
运行时间与返回结果的保证
命题 7.1.9
(算法的成本)
设 。算法最坏时间为 ,除输入图外,辅助的距离存储量为 。
证明
(计算边的检查次数)
初始化花费 。至多 次主要扫描及一次检测扫描,各检查 条边记录,每条为常数时间,合计 。距离数组有 项。
图至少有一条边时,常简写为 ;但 时,仍要计算初始化的 。如果保留边数表的所有行,则需 距离存储量;原地算法不需要该表。
实现要么返回正确源点距离,要么警告存在某个可达负环。环的具体证据、重建最短路径,以及列出全部距离为 的顶点,都是需要额外记录的输出。尤其如果要分类受影响顶点,可从主要扫描后仍可松弛之边的终点开始,遍历所有从它们可达的顶点。这是额外分类步骤,不能单凭每个当前有限标签完成。
常见错误
常见错误
(把“至多”改成“恰好”)
如果把 定义为恰好使用 条边的游走之最小权重,递推式就失去第一项。只有一条权重为 的边 时,,因为不存在恰好两条边的游走,但 。“至多 条”的上限让较短的游走仍然可用。
常见错误
(用大整数代替 INFINITY)
假设不可达顶点的标签为 ,而权重为 的边 连接两个不可达顶点。检查 成立,于是 得到一个虚假的有限标签。如果 的权重为 ,标签就不断改变。伪代码中的有限前驱检查正是为了防止这种情况。
常见错误
(检测失败后仍返回标签)
取边 权重 、 权重 、 权重 ,按此顺序扫描,。两轮后对 有 ,第三轮会令两者都变成 。检测测试发现 可松弛。这些有限标签不是距离:真值是 ,算法必须报告负环。
有解练习
快速检查
(计算边数表时,不使用新的一行)
取顶点 ,边为 权重 、 权重 、 权重 、 权重 。按顶点顺序 求 各行,并给出一条到 的最优路线。
解答 · 答案
各行为 、 及 。边数上限二时,尚不能把 的新值延伸到 ;6 来自前一行的 4。上限三时, 给出 。图中没有环,且三等于 ,所以最后一行已是真正距离。
快速检查
(边顺序改变一轮内的传播)
在路径 上,三条边权重均为 1,从初始距离数组开始。比较按前进顺序及反向顺序做一次原地边扫描的结果。它们是否与边数递推式矛盾?
解答 · 答案
按 顺序,前进扫描得到 ,因为每个新值立即重用。反向扫描先遇到两条起点不可达的边并跳过,最后才处理 ,得到 ,这恰好等于 。两者都不与递推式矛盾:原地证明只要求一轮后 ,且每个有限标签有实际游走作证。前进扫描的结果在 和 处小于 ,这是允许的;此处它等于 。
快速检查
(可达性决定哪个负环有影响)
只有以下边: 权重 2、 权重 、 权重 1、 权重 7、 权重 、 权重 1。从 出发,哪些顶点的距离为 、有限值或 ?Bellman–Ford 报告什么?
解答 · 答案
可达环 的权重为 ,所以 的距离为 。它们不能到达 或 ,后两者距离分别为 0 及 7。 不可达,距离为 ,即使它们的分量本身也有负环。Bellman–Ford 因 报告有可达负环;基本警告本身不提供这份完整分类。
快速检查
(负自环与零权重环)
如果 ,唯一顶点为 ,主要扫描进行多少次?如果有权重为 的自环,会发生什么?如果权重改为 0 呢?
解答 · 答案
主要扫描有 次,但仍会进行检测扫描。权重为 时,检查得到 ,正确报告有可达负环;从 到自己的距离为 。权重为 0 时没有严格改善,距离为 0。零权重环允许无限多条相同权重的游走,却不会使权重无下界。