CSCI3160 Regular 9：最短路正确性、负环与重赋权

原件：题目（本地课件）；官方答案（本地课件） p.1–4。 定位：区分候选距离与真实距离，明确非负边、可达性和负环分别在哪一步起作用。

记真实最短距离为 δ(v)，算法当前估计为 d(v)。源点无法到达的点距离为正无穷。以下“最短路径存在”的论证都限定目标可达；原题部分语句未明确此条件。

Problem 1：Dijkstra 的正确性（答案 p.1–2）

基本不变量：每个有限 d(v) 都是某条已找到的源点到 v 的路径或游走长度，所以 $d(v)\ge\delta(v)$。松弛只会降低上界，不会把距离变成比真正最短距离更小的数。

归纳证明每次取出的最小 d 顶点 u 已满足等号。第一次取源点 s，d(s)=δ(s)=0。假设之前取出的点均已正确，考虑下一点 u。若可达，在某条到 u 的最短简单路径上，令 y 是第一个还没确定的顶点，x 是它的前驱；x 已确定，松弛 x→y 时得到 $d(y)\le\delta(x)+w(x,y)=\delta(y)$。结合上界不变量，d(y)=δ(y)。

u 是当前最小估计，故 $d(u)\le d(y)=\delta(y)$；非负边使最短路径后缀长度非负，所以 $\delta(y)\le\delta(u)$。连起来：

所有不等式只能取等号。零权边造成相等也无妨，不需要假定严格递增。若队列最小值已是无穷，却还存在可达未确定点，则在其最短路径上同样能找到一个有有限候选值的首个未确定点，矛盾。因此剩余点均不可达。

自取边 s→a 重 2、s→b 重 5、a→b 重 1：先确定 s，再 a，将 b 的候选从 5 降到 3，再确定 b。正确性的关键不是“猜最小者通常靠谱”，而是上述上下界被夹到同一数值。

官方勘误。 答案 p.2 最后一段将候选与真实最短距离的大小方向写反；应当是候选不能小于最短距离。本文给出的不等式链同时覆盖零权情形。

Problem 2：非负条件到底用在哪里（答案 p.2）

用在 $\delta(y)\le\delta(u)$：路径从 y 走到 u 的后缀若每条边非负，总和就不可能为负。若含负边，某个当前看起来很远的未确定顶点，可能通过负边抵达已经取出的顶点并产生更短路线。

自取 s→a=2、s→b=5、b→a=−4。Dijkstra 会先确定 a=2，真实最短却是 s→b→a，长度 1。注意图无环，当然也无负环，因此“没有负环”不足以保证 Dijkstra 正确。

Problem 3：无负环时存在简单最短路径（答案 p.2）

对可达 s,t，取一条最短游走，并在所有最短者中选边数最少的一条。若重复顶点，重复位置之间构成闭合游走，可以分解为若干简单环；无负环保证其总权重非负。删掉这段后，若权重下降，就与原先最短矛盾；若权重不变，就与“最短者中边数最少”矛盾。因此该游走没有重复顶点，是简单路径，最多 n−1 条边。

这只是说存在一条简单最短路径，不是说所有最短游走都简单。零权环可以绕任意多次而不改变最短长度。若 t 不可达，则不存在任何路径，不能仍断言“至少存在一条”。

Problem 4：DAG 上允许负边的线性 SSSP（答案 p.2–3）

先拓扑排序，初始化 d(s)=0、其他为无穷。按拓扑序处理每个 u，若 d(u) 有限则对所有 u→v 做 $d(v)=\min(d(v),d(u)+w(u,v))$，严格变小时保存前驱 u。

因为所有到 v 的最后一条边都来自拓扑序更早的点，处理 v 时所有可能前驱均已处理完，候选已枚举完整。因此负权也无妨，关键是无环保证依赖有合法先后顺序。每条边一次松弛，时间 O(n+m)，前驱数组空间 O(n)。

例：s→a=2、s→b=5、b→a=−4。拓扑序 s,b,a，先完成 b 再处理 a，得到 a=1。它与 Q2 的错误执行使用同一输入，清楚显示安全处理顺序的作用。源点不必是全图唯一入度零顶点；源点之前不可达的顶点跳过即可。

Problem 5：重复的简单最短路命题（答案 p.3）

本题与 Q3 命题实质相同，仍需可达性前提。独立证明可用“不断删除重复顶点之间的闭合段”：每段权重非负，删去不会增加总代价。若从最短游走出发，删去后不可能更短，否则原来的不是最短；因此每次保留最短性，却减少边数。有限次删除后得到简单最短路径。

自取 s→a 权重 2、a→b 权重 1、b→a 权重 −1、a→t 权重 3。s,a,b,a,t 长度 5，其中环长 0；删环得到 s,a,t，长度仍 5。这个例子同时说明允许负边与禁止负环不矛盾。

Problem 6：原算法只能检测源点可达的负环（答案 p.3–4）

题面从任意一个 s 设距离 0，其余无穷，运行 n−1 轮，再检查是否仍可松弛，要求判断全图是否有负环。按原条件，这个结论不成立。

反例：三个顶点 s,a,b，s 孤立，a→b=−1、b→a=0。图含负环，但 a、b 始终为无穷；按扩展运算，无穷加有限数仍无穷，不存在严格改善，算法错误报告无负环。

修正之一：增加超级源点，向全部原顶点连零权边，再检测。等价的省空间初始化是所有原顶点 d=0，执行 n−1 轮原边松弛，再检查下一轮。此时每个分量均可达。

为什么修正版正确？若无负环，最短简单路径最多 n−1 条边，n−1 轮足以传播；稳定后每条边满足 $d(v)\le d(u)+w(u,v)$。反过来，若某个负环上所有边都满足该不等式，把它们沿环相加，左右的有限距离相互抵消，得到 $0\le\sum w(e)$，与负环权重和小于零矛盾。因此至少一条环边仍可改善。

官方证明直接把环上距离相加并相消，遗漏了距离可能为无穷、此时不可相消的问题。若只要求判断“从 s 可达的负环”，原算法本身正确。算法时间 O(nm)，额外距离空间 O(n)；别把一次完整扫描误叫作单条边松弛。

补充：把不可达负环反例真的运行两轮。 原Q6反例有3点，应做2轮。初始(s,a,b)=(0,∞,∞)，先扫a→b:-1，再扫b→a:0；两条边的起点都不可达，第一轮仍(0,∞,∞)，第二轮也一样，额外扫描不能严格改善。若改为全零初始化，第一轮a→b使b=−1，b→a使a=−1；第二轮得a=b=−2，额外扫描继续下降。两种初始化分别回答“源可达负环”和“全图负环”，差异可直接从表上看见。

Problem 7：Johnson 重赋权为何非负（答案 p.4）

超级源点 q 向所有顶点连零权边，令 h(v)=δ(q,v)，所有 h 均有限。最短路的三角不等式给出 $h(v)\le h(u)+w(u,v)$，移项即

这里是把到 u 的最短路线再接 u→v，与到 v 的真正最短路线比较；不要求这条接出的路线自己最短。自取 h(u)=−2、h(v)=−5、w(u,v)=−3，则新边权 0；原边为负也完全可能。

Problem 8：原边非负时重赋权不改变它（答案 p.4）

超级源点到每点都有直接零权边，所以 h(v)≤0；全图边权非负又保证任意路线长度≥0，因此 h(v)=0。代入 Q7 得 $w'=w+0-0=w$。不能只由“有零边”推出最短距离是零，另一条含负边的路线可能更小；此题明确非负才使两个方向夹住零。

来源与证据

官方答案 p.1–4；Q6 给出原命题反例与两种修正。Q3、Q5 保留原题号，不因题目重复而省略。本文不据练习推断考试范围。