距离的含义
路网可能有负边成本,例如某次转换给予回扣。依赖非负权重的贪心最短路径论证便可能失效。我们改用受限边数构造最佳游走,并另外检测何时可达负环能重复经过,使有限最小值不存在。
定义 4.2.1
(游走距离与负环)
设 是有限有向图,有 个顶点、 条边、每条边 的有限实数权重 和源点 ;允许不同权重的平行边及自环。游走可重复顶点和边。从 到自身的空游走权重为零。每个顶点的距离定义为所有源点至该顶点游走权重的下确界;若没有游走,记作 。负环是总权重为负的有向环(除端点外不重复顶点的闭游走;自环也算)。
若某顶点可由源点可达的负环走到,其距离是 :先绕环任意多次,再走到该点即可。这不表示某条有限游走的权重等于 。
反例模式
遇到负边,确定最近顶点的做法会失败
取权重 的边 、权重 的边 ,以及权重 的边 。在非负权重下适用的贪心规则会先确定最近的顶点 ,距离为 ,因为其他游走似乎都以不短于它的一段开始。但游走 的权重是 ,所以到 的真实距离是 ,先前确定的值是错的。“之后的边不能缩短已确定顶点的距离”这个论证需要非负权重。下面的按边数递推不会提前确定任何顶点:按 的顺序,,而 。
按边数动态规划
定义 4.2.2
(边数受限的距离)
令 为从 到 使用至多 条边的游走之最小权重;若不存在则为 。初始化 ,并对 设 。
命题 4.2.3
(按边数的递推式)
对 ,
空的内层最小值为 ,而 加有限权重仍为 。
证明
(在最后一条边处拆开游走)
从 到 、至多 条边的游走,要么至多有 条边,贡献 ;要么恰有 条边,并以边 结尾。后一种情形下, 之前的部分是从 到 、至多 条边的游走,其权重至少为 ,因此整条游走的权重至少为 。所以右边是每个候选的下界。反过来,把任何边 接在达到 的、至多 条边的游走之后,得到一条至多 条边的有效游走,所以右边的每一项都由真实的游走达到。有限图中边数受限的游走只有有限多条,因此每个有限最小值都会被达到。从基础行 开始对 作归纳,即证明递推式精确算出每个 。
使用前一行及下一行两个数组:先复制前一行,然后扫描每条边,但只读取前一行的值。这使其含义不依赖边的扫描次序。
命题 4.2.4
( 轮之后的有限距离)
若没有源点可达的负环能走到 ,则到 的距离等于 ;当 可达时它是有限的,否则为 。
证明
(删去非负的环,只剩简单路径)
在此假设下,每条源点至 的游走上,所有环的权重均非负。从游走中删去一个环不会增加权重,重复删除便剩下至多 条边的简单路径。因此对所有游走取的下确界,等于对至多 条边的游走取的最小值,即 ,并且会被达到。不可达的 没有游走,保持 。这是针对 的条件:其他地方有负环,不代表所有距离都无下界。
检测及传播负环影响
定理 4.2.5
(额外一轮与受影响顶点)
算出 后再同步扫描一轮得到 。存在源点可达负环,当且仅当至少一个顶点满足 。令 为所有这类顶点,则能从 到达的顶点恰好是距离为 的顶点。
证明
(改进迫使有环,有负环也迫使有改进)
一方面,若 ,见证改进的最小游走必有 条边,故重复某个顶点。若游走上的每个环均非负,删掉一个环便得到至多 条边且权重不更大的游走,矛盾。因此某个可达负环能走到 。
另一方面,可达环的每个顶点都有至多 条边的简单源点路径,所以 有限。若某个可达负环上的顶点在额外一轮全没有改善,则对每条环边 ,递推式给出 。沿环求和会迫使总权重非负,矛盾。因此每个可达负环至少有一个顶点属于 。从 所有顶点出发的图遍历,恰好标记可在这类环之后到达的顶点。不可达负环的前驱值保持 ,不会造成改进。
证明透视
额外一轮的证明在哪里转折
不明显的一步是沿环的叠加求和。没有改进,就表示沿环的每条边都已有不等式 ;把这些不等式相加,所有 值互相抵消,剩下 。这个抵消之所以合法,是因为可达环上的每个值都是有限的,所以证明先为环上每个顶点记下有限的 。在不可达的环上,各值是 ,不等式 不带任何信息,而那里的负环也确实从不会被检测到。
另一个假设是数目 :有 条边的游走经过 个顶点,因此必定重复某个顶点,而这个重复就是可以被剪掉的环。这就是为何检验要看 条边的游走:至多 条边的游走可以是简单路径,完全不含环。这一轮必须是同步的,因为证明把 读作关于至多 条边的游走的陈述。全文也假设权重有限,因为上面的抵消需要实数的和。
逐轮例子
例题 4.2.6
(有负边但没有负环)
取顶点 ,边为权重 的 、权重 的 、权重 的 、权重 的 、权重 的 。按 的顺序,各行是
额外一行 不变。到 的最佳游走为 ,权重 。允许负边;单有负边不等于有负环。
例题 4.2.7
(只有额外一轮才揭示的负环)
取顶点 ,边为权重 的 、权重 的 、权重 的 和权重 的 。环 的权重是 。按 的顺序,同步各行是
此时 ,额外一行是 ,而 ,所以 。顶点 与 在这一轮没有改进,但两者都能从 到达,因此遍历把 都标记为距离 。源点保持 ,因为没有边回到它。
例题 4.2.8
(单一顶点与自环)
取 ,只有源点 。此时 ,额外一轮是 。若 有权重 的自环,则 ,所以检测到该环, 的距离为 。若自环的权重为 或任何正数,则 ,不报告负环,距离为 。零权重的环不是负环,不会影响有限性。
反例模式
可达负环只影响其后继
令 权重为 , 为 , 为 , 为 。环 权重为 ,故 的距离为 。若没有边回到 ,它的距离仍为 。孤立顶点 不可达,距离是 ;不可达负环也不能影响源点距离。
常见错误
(只报告最后一行而没有做额外一轮)
经过 轮后,表中每个值看上去都像有限的答案,但负环仍可能藏在里面。在上面的负环例子中, 看似一张有效的最短距离表,可是到 的真实距离全都是 。只有把 与 比较,才会显示出来。
常见错误
(把原地更新的数组当作按边数的一行)
若第一个例图的边按 、、 的顺序扫描,并把更新写回同一个数组,那么一轮之后 的值已经是 ,但 :更新在一轮中走过了三条边。原地扫描仍然会收敛,可是它的值不能解读为至多 条边的距离,所以额外一轮的检验必须比较真正同步的各行。
成本与范围
命题 4.2.9
(按边数算法的运算数)
算出 并标记受影响顶点,需要 次算术及比较运算,以及输入图以外的 工作空间。
证明
(先数轮数,再加上一次遍历)
一轮同步计算复制 个值并扫描 条边,成本为 。算到 共有 轮,共计 。两个距离数组需要 额外空间。以邻接表从 向前遍历需 ,不改变上界。若保存每行以重建边数受限的游走,则需更多空间。这是把实数算术视为常数成本的运算数,不是任意编码下的位复杂度保证。
练习
快速检查
(在第一个例图中,为何 而 ?)
数一数到 的各条路线各用几条边。
解答 · 答案
至多两条边时, 的成本是 ;更便宜的 成本是 ,但需三条边。
快速检查
(若 的权重为 ,而 有权重 的自环,则 的距离是多少?为什么?)
自环也是一个环。
解答 · 答案
为 :到达 后可任意重复自环,使游走权重无下界下降。
快速检查
(负环不可由 到达;这件事本身是否会使源点距离变成 ?)
想想源点游走能否进入该环。
解答 · 答案
不会。源点游走无法进入该环,因此无法在源点至某顶点的游走上重复它。
快速检查
(若要把额外一轮解读为 ,为何应使用新数组?)
想想原地写入会对同一轮中之后的边产生什么影响。
解答 · 答案
原地更新可能在一轮中按边顺序传过多条边;分开数组才能保证证明所用的至多 条边递推。