动机
单源最短路径算法只能给出从某个起点出发的距离,但有时需要求出每一对有序顶点之间的距离。Floyd–Warshall 算法围绕“哪些顶点可以出现在路径内部”来组织问题:在每一阶段,它考察多允许一个顶点作为中间顶点后,某个距离是否能够改进。
本单元允许负权边,但不允许负权环。若没有这一假设,有限的最短距离未必存在:反复绕行一个可达的负权环,可以使途径的权重无限下降。我们把不可达的顶点对的距离视为 。
定义
定义 3.6.1
(经中间顶点的距离)
设 是顶点为 的有限有向图,边权为实数,且不含负权有向环。平行边可以用其中权重最小的一条代替。途径的权重是其各边权重之和。从某顶点到其自身的长度为零的途径,权重为零。对 ,定义 为从 到 且内部顶点均属于 的途径的最小权重;端点不受限制。若不存在这样的途径,则取值 。
初始化时,令 ;对 ,令 为最轻的直接边的权重,若无边则为 。在没有负权环的前提下,自环的权重非负,因此对角线取零长度途径的初始化是正确的。计算候选值时,对有限的 约定 。
定理
定理 3.6.2
(中间顶点递推式)
对 ,
第 阶段之后,这些元素即为全源最短途径距离。
定理 3.6.3
(原地计算)
从 出发,依次处理 ,并对每个有序对 ,将 替换为 。在无负权环的假设下,所得结果等于 。该算法使用 次算术/比较运算和 个距离元素。
证明思路或证明
证明
(在新顶点处分割最短途径)
在没有负权环时,只要存在任何允许的途径,就存在权重最小的允许途径:不断去掉含重复顶点的、权重非负的环,直到剩下一条简单路径。若某条最短路径内部不出现 ,则其代价至少为 。否则取一条最短简单路径,它至多经过 一次,在 处将其拆开。两段子路径的内部顶点都属于 ,所以其代价至少为 。当 是端点时,同样的推理仍然成立,只需用一段零长度子途径。
反过来,实现第二项两个距离的任意两条途径,可以在 处连接起来,得到第 阶段允许的一条途径。第一项对应的途径同样是允许的。若某一项为无穷,则它不提供有限的候选值。这两个不等式证明了递推式。在第 阶段,所有顶点都可以作为内部顶点,因此得到不受限制的最短途径距离。
证明透视
无负权环的假设用在何处
不显然的一步,是先取一条最短的简单途径再分割:这样 至多出现一次,两半的定义才明确,而且各自的内部顶点都在 之中。无负权环的假设正用在这里,用来说明去掉环不会增加权重,所以存在简单的最小者。相反方向的上界则无需这样小心,因为在 处连接两条允许的途径,即使结果有重复顶点,仍然是允许的。论证对阶段 归纳,从第零阶段的直接边表出发;到第 阶段,内部顶点不再受限。若没有这个假设,分割就失去意义,因为最小值不存在,下面的反例正说明这一点。
证明
(阶段内的行和列保持不变)
对于原地更新:对角线始终为零,因为权重为负的闭途径必然包含负权环,而这已被假设排除。在第 阶段,更新 时是将它与 比较;更新 时同理,它也保持不变。因此在整个阶段中,用来产生候选值的第 行和第 列保持其第 阶段的取值。其余每个单元都恰好用这些不变的元素,从其先前的值更新一次,这正好实现了递推式,且与 的处理顺序无关。三重嵌套循环给出运算次数的界,而表中共有 个元素。
证明透视
为什么这里原地更新是安全的
证明需要第 阶段的行和列在其他单元更新期间保持不变。由无负权环假设保证的零对角线提供了这一不变量。
例题详解
例题 3.6.4
(中间顶点改进了一条路径)
设 的权重为 , 的权重为 , 的权重为 。允许 作为中间顶点,会得到候选值 ,所以从 到 的距离变为 。当不存在负权环时,负权边不会影响这一推理。
例题 3.6.5
(不可达的顶点对)
若既没有从 到 的直接边,也没有任何途径能从 到达 ,则每个包含不可达段的候选值都是 ,最终元素仍为 。在没有证明某个有限数大于所有相关的有限路径代价之前,不可以把它换成一个很大的有限数。
常见错误
常见错误
(把每条负权边都当作负权环)
权重为 的边不一定使最短路径问题失效。问题出在存在一个可达的环,可以重复绕行且总权重为负。含 的那个例题中有负权边,但在所示的图里没有环。
反例模式
放弃无负权环的假设
断言:递推式对任何实数权重的有向图都能算出最短途径距离,包括含负权环的图。取两个顶点 ,边 的权重为 ,边 的权重为 ,这个环的权重为 。重复走这个环,得到从 到自身、权重为 的途径,因此这一对没有有限的最小值。原地算法按行优先顺序处理各对时,从 出发,最后得到 :对角线元素为负,所以这张表并不是距离表,而且结果取决于循环恰好运行了多少步。修正方法是保留假设:不存在权重为负的有向环,或另用算法去检测这样的环。
该定理计算的是距离;若要重构路径,还需要额外的前驱信息,并需要仔细处理并列的情形。
反例模式
把阶段下标放在最内层
断言:三重循环可以按任意顺序嵌套,例如把 放在最内层,只扫描一遍仍得到距离。取顶点 ,边 、、 的权重都是 ,因此从 到 的距离是 。若 为最内层循环,各对 按行优先顺序处理,则在求 时, 与 尚未得到改进后的值 和 :候选值为 与 ,所以它仍是 ,而第 行不会再被处理。修正方法是采用所述的嵌套,以阶段 为最外层,先完成阶段 的所有顶点对,再进入阶段 。
正确理解状态
下标 限制的是内部顶点,而不是端点。在第零阶段,直接边没有内部顶点,即使某个端点的编号很大,它也是允许的;零长度途径同样是允许的。在第 阶段,端点 和 可以等于 ;由于在假设下对角线距离为零,递推式仍然有效。
动态规划的不变量是:完成第 阶段后,每个表项是仅以顶点 作为内部顶点时的最优距离。这并不意味着这些顶点必须全部被用到。多允许一个顶点,只会使距离保持不变或变得更好,因此 。若某次计算使一个有限的表项变大,则说明它违背了递推式。
例题 3.6.6
(一个完整的三顶点表)
设顶点依次为 ,边为: 权重 , 权重 , 权重 , 权重 。两个有向环的权重分别为 和 ,所以不存在负权环。初始表为
允许 后, 的代价为 。允许 后, 的代价为 。允许 后, 的代价为 。最终的表为
未提及的元素保持不变。每一次改进都有一条实际连接而成的途径作为依据。
概念视角代数
同一张表看成矩阵乘积
把加法换成取最小值、乘法换成加法:两张表的乘积定义为 。设 为初始表,则 给出至多两条边的最佳途径, 给出至多 条边的最佳途径;由于最短途径可取为简单路径,这已足够。因此在这种乘积下 。在三顶点例子中, 已等于最终的表。
一个表项可能有多条取到最小值的途径。递推式只需要最小权重,所以并列时可以不作更新。若还要求给出路径,可以另设一个见证结构,记录一条直接边或一个起改进作用的中间顶点。要从最终的原地表重构路径,必须为这些见证建立不变量,特别是在存在零权环或并列路径时。本单元证明的是距离的计算,并不声称某种具体的路径重构实现是正确的。
为什么可以去掉环
任何闭途径都可以分解为若干有向环。在假设之下,每个这样的环权重非负,所以去掉一段含重复顶点的闭途径段,不会使途径的总权重增大。重复这一操作,在两端点不同时得到一条简单路径,在两端点重合时得到空途径。去掉顶点不会引入允许集合之外的内部顶点。由于有限图中固定一对顶点之间只有有限多条简单路径,只要这一对顶点可达,最小值就存在。
这一论证允许零权环。去掉一个零权环后,权重可能保持不变而不是严格减小,但仍然得到一条取最小值的简单路径。负权边同样是允许的:关键在于每个有向环的总权重。只要不存在可重复绕行、使下确界无下界的负权闭途径,最短简单路径就可以包含负权边。
递推式中上界方向使用的是连接操作,即使每一段都是简单的,连接后的途径也可能含有重复顶点。这在 的定义中是允许的。连接后的途径满足内部顶点的限制:连接点是 ,其余内部顶点都出现在两段子途径之一中。如有需要,还可以去掉非负权环而不增加其权重。这就是两个不等式能够配合起来、而无需假设连接结果本身是简单路径的原因。
三重循环的下标
外层下标决定允许作为中间顶点的集合。对固定的 ,两层内循环枚举所有起点和终点。由于第 行和第 列在该阶段内不变,在定理的假设下,内两层循环采用任一顺序都可行。若把 移到其他循环的内层,就不再能保证每一对顶点按预期的顺序看到所有路径;这需要另外的证明,并可能得到不同的结果。
无负权环的假设被用到两次:它保证可达顶点对的有限最小值存在,并使原地计算全程保持 。它的作用不仅是拒绝带负权边的输入。若图中可能含有负权环,就必须说明期望的结果是检测负权环、对不受影响的顶点对给出有限距离,还是对能到达并离开这类环的顶点对给出 。这些输出规格相互关联但并不相同,相应的算法需要额外的证明。
无穷大的表示与代价度量
常见错误
(用有限的哨兵值代表无穷大)
数学上的 是一个特殊值,而不是普通整数。在代码中,带保护的加法可以在任一加数为无穷时返回无穷。若使用一个固定的很大哨兵值,再加上负权边的权重,就可能得到误导性的有限值,除非溢出和所有有限距离的界都得到控制。精确实数下的递推式不存在这一表示问题;而具体实现必须明确处理它。例如,以 代表无穷大。若 不能到达 ,而边 的权重为 ,则候选值 小于 ,于是一个不可达的顶点对被赋予一个有限的距离。
的计数把有限边权的加法和比较视为单位运算。若有理数权重以二进制编码,还必须考虑其精确算术代价和位长。即使原图的边很少,该方法也要存储一个稠密的 表;重复运行单源算法,在资源上可能有不同的取舍。该定理并不声称稠密的全源表总是最高效的表示。
当 且没有负权自环时,初始化给出 的表 ,唯一的阶段不改变它。对于不连通的图,一些元素保持无穷,另一些元素是有限的。这些情形都属于同一个不变量;不会在各连通分量之间引入人为的路径。
检验结果
一个有限的表项可以由具有该权重的一条显式途径支撑,这给出最短距离的一个上界。要证明该表项同时也是下界,则需要依靠动态规划的不变量,它考虑了每一个允许的中间顶点。仅仅找到一条较短的途径,并不足以证明不存在更短的途径。反过来,一个不可达的表项需要可达性论证,而不是对少数几条候选路径的搜索未果。
在三顶点的例子中,从 到 的表项有见证 ,权重为 。从 到 的表项有见证 ,权重为 。完整的递推式确立了不存在更便宜的途径。见证有助于发现算术错误,但不能替代递推式的证明。
总结
状态 把内部顶点限制在前 个顶点之内。最短路径要么在内部不经过 ,要么在 处被拆开。在没有负权环时,第 行和第 列在该阶段保持不变,从而允许标准的原地三次方算法。
练习
快速检查
(若 ,,,则 是多少?)
把旧值与经过 的和作比较。
解答 · 答案
它等于 。
快速检查
(对于之间没有任何有向途径的顶点对,用什么值表示?)
考虑根本没有途径的情形。
解答 · 答案
该值为 。
快速检查
(为什么零长度途径使每个初始对角线元素至多为零?)
数一数没有边的途径。
解答 · 答案
从某顶点到其自身的零长度途径权重为零;在没有负权环时,不存在权重更小的闭途径,所以对角线恰好为零。
快速检查
(一条负权边是否必然产生负权环?)
考虑只有一条边的图。
解答 · 答案
不一定。若图中只有一条权重为 的有向边且没有返回路径,则图中根本没有环。