CSCI3160 T10 负环检测与恢复

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T10 负环检测与恢复 · 原件 T10-负环检测-未核-隐藏.pdf（本地课件） p.1–34 定位：辅导；先恢复最短路径树，再检测负环，最后讨论不要求考试的负环恢复。

p.1–3 从距离恢复到具体路径【延伸 L14 p.10–25】

p.1 是标题页。p.2 先区分两个输出：检测只回答有无；寻找必须列出一条真实的有向负环。两者都使用 Bellman–Ford，不能因为能检测就声称已经输出了环。

p.3 回顾最短路径树：距离数组只告诉你长度，父指针才告诉你最后一步来自哪里。源点父指针为 nil；严格改善顶点的距离时才更换父亲。这里承接 L14。

p.4–6 一次松弛更新两个量

p.4 的条件是严格大于。满足条件时同时令距离等于候选值、parent(v)=u；相等时保持原父亲，避免凭等长候选无意义地改树。p.5 初始化源点 a 为 0，其余为无穷，重复扫描全部边六轮，因为例图有七个顶点。

p.6 给出无负环的图和固定扫描顺序：fe、dg、ad、ab、bc、cd、ce、gf、ed。这里的 ad 权重为 −6，方向是 a 到 d。顺序会影响每轮的中间值，不影响无负环时充分轮数后的正确答案。

原图完整边权为 fe=1、dg=−3、ad=−6、ab=1、bc=1、cd=−2、ce=−1、gf=2、ed=5；后文负环版本只把 ad 改为 da，边权仍为−6。

p.7–9 第一轮的前三条边

p.7 扫 fe 时 f 尚不可达，不能从无穷得到有限候选。p.8 扫 dg 同理。p.9 扫 ad，候选为 0−6=−6，故 d 从无穷改为 −6，父亲改为 a。注意 dg 已经扫描过，即使现在知道了 d 的值，也要等下一轮才通过这条边传播。

p.10–12 沿扫描顺序即时传播

p.10 的 ab 令 b=1、父亲 a。p.11 紧接着的 bc 使用刚更新的 b，令 c=2、父亲 b。这是一轮内即时更新，不是整轮结束才交换新旧数组。p.12 的 cd 给 d 的候选值 2−2=0；现有 −6 更小，因此不更新，d 的父亲仍是 a。

p.13–15 第一轮结束

p.13 的 ce 给 e=2−1=1、父亲 c。p.14 的 gf 因 g 仍为无穷而无效果。p.15 的 ed 给 d 候选 1+5=6，大于 −6。按 a、b、c、d、e、f、g 排列，第一轮结束为 (0,1,2,−6,1,∞,∞)。沿 parent 回走，e 目前对应 a→b→c→e，长度 1。

p.16–18 后续轮怎样稳定

p.16 图展示第二轮结束后的标签。

p.16 第二轮先扫 fe，仍无效果；接着 dg 把 g 改为 −6−3=−9、父亲 d。轮末 gf 把 f 改为 −9+2=−7、父亲 g。e 尚为 1，因为 fe 已扫完。

p.17 第三轮开头 fe 给 e 候选 −7+1=−6，优于 1，父亲由 c 改为 f。p.18 第四至六轮没有变化。最终距离为 (0,1,2,−6,−6,−7,−9)。这里说明“一轮遍历了所有边”不等于“所有路径都传播完”：前后次序可以让同一路径跨多轮推进。

p.6–18 的完整距离与父亲变化表如下，距离列始终按 a,b,c,d,e,f,g 排列；“父亲变化”只列本步新增或改写，其余继承。

p.19–21 树已能恢复，检测要多看一轮

p.19 的父边构成 a→b→c 与 a→d→g→f→e。回走 e、f、g、d、a 后反转即可得到 a 到 e 的路径；边权 −6−3+2+1=−6，和距离一致。

p.20 切换到允许负环，并假设图强连通。这个假设保证任意环都能从源点到达；没有它，单源初始化只能检查源点可达部分。p.21 先做普通的六轮，再扫描各边：只要某条仍可严格改善，就报告存在负环。这次额外扫描是检测，不要求真的继续更新全部距离。

p.21 完整检测流程：

任选源点 s；dist[s]=0，其余∞；所有 parent=nil
重复 |V|-1 轮：
  扫每条边 (u,v)：
    若 dist[u] 有限且 dist[v]>dist[u]+w(u,v)：
      dist[v]=dist[u]+w(u,v)；parent[v]=u
再扫描每条边 (u,v)：
  若 dist[u] 有限且 dist[v]>dist[u]+w(u,v)：返回“有负环”
返回“无负环”

强连通是此版输入条件。对任意图检测全图负环，可添超级源点到每点的零权边，或等价地将所有点初始距离设为0再用原顶点数轮数；也可先求 SCC，再逐分量检测，因为任何环全部位于同一 SCC。这补答 p.20 的多分量问题，不能只随意选一个原点而漏掉不可达负环。

p.22–24 反转一条边便出现负环

p.22 将原先 a→d 改成 d→a，仍重 −6。因而 d→a→b→c→d 总重为 −6+1+1−2=−6，能反复降低代价。扫描顺序改为 fe、dg、da、ab、bc、cd、ce、gf、ed。

p.23 第一轮先无法使用 da；随后 ab、bc、cd 使 b=1、c=2、d=0，ce 使 e=1，f、g 仍无穷。p.24 第二轮 dg 先给 g=−3，da 给 a=−6，再一路把 b、c、d、e 更新为 −5、−4、−6、−5；gf 给 f=−1。整轮向量是 (−6,−5,−4,−6,−5,−1,−3)。源点距离也会下降，不能强行每轮把它重置为 0。

负环版 p.23 的父亲向量为 (nil,a,b,c,c,nil,nil)，p.24 起至 p.28 的父亲向量为 (d,a,b,c,c,g,d)，全部按 a,b,c,d,e,f,g 顺序。这与前述每轮距离向量一起给出了源页整张表，而不仅是变红的数字。

p.25–27 六轮后仍没有“最终最短距离”

p.26 图展示第六轮结束后的标签。

p.25 第三轮为 (−12,−11,−10,−12,−11,−7,−9)。绕负环一圈又少 6；p.26 第六轮得到 (−30,−29,−28,−30,−29,−25,−27)。这些是算法当前标签，不是有穷的最短路答案。

p.27 开始额外扫描，fe 的候选 −25+1=−24 大于 e 的 −29，因此第一条边没有触发检测。负环存在不意味着每一条边都还能改善。

p.28–30 第一条仍可改善的边就是证据

p.28 的 dg 候选 −30−3=−33，小于现有 −27，因此报告负环。p.29 把正确性拆成双向命题，不能只证明其中之一。p.30 证明“触发检测就有负环”：若没有负环，存在至多六条边的最短简单路径；Bellman–Ford 六轮后已经得到它们的距离，任何边都不能再改善，矛盾。

p.31–33 为什么有负环一定触发

p.33 “You will not be tested on the rest of the slides.”

p.31 假设有负环却所有边都不能改善。于是环上每条 u→v 都满足 dist(v)≤dist(u)+w(u,v)。p.32 将这些不等式相加，每个顶点的距离在两侧各出现一次、可以抵消，得到 0≤环总重；这与负环定义矛盾。这里必须是有限距离；用无穷相减不是证明。

一般环 $v_1\to\cdots\to v_\ell\to v_1$ 的求和写为

消去同一时刻的有限距离和，得到 $0\le w(C)<0$（C 表示该环） 的矛盾。

算一遍：例环有四条不等式，把左侧 a、b、c、d 的距离与右侧同四项抵消，只剩 0≤−6，明显不成立。因此至少有一条边触发。p.33 给出范围边界，接下来“输出负环”的细节明确不在此辅导要求的考试部分。

考试角度：（B 级：T10 p.33）检测与后续寻找环须分开，不能把后者标成讲义要求考查的步骤。

补充：检测给出矛盾，恢复给出可检查对象。 “dg 仍可改善”可以证明某处有负环，却不意味着 dg 自己在负环上；它可能只是负环把越来越小的距离传向下游的边。要输出证书，需沿父链找到重复段、反转方向，再逐条查这条有向环的原权总和严格小于0。

p.34 从可改善边追到真正的环【新】

检测边是 d→g，于是把 g 的父亲设为 d。沿父指针走 g,d,c,b,a,d，第一次重复的是 d。删去进入环前的 g，保留 d,c,b,a,d，然后反转得到原图中的有向环 d→a→b→c→d。g 只是受负环影响的下游点，不能把它也输出成环的一部分。

补充：用“顶点是否访问过”和首次位置数组记录这条链，每个顶点至多首次进入一次，追踪为线性时间；每步从头搜索已有列表会退化。完整证明和原件伪代码中输出语句的歧义见 T10-proof。

多个分量的检测范围见附录 A1。

本讲核心考点

• 父指针只随严格改善而更新，恢复时逆向回走再反转（p.3–19；C 级）。
• 无负环时完成顶点数减一轮后不再可松弛；负环上的不等式相加给出反证（p.20–32；C 级）。
• 单源检测的范围是可达部分；强连通假设保证覆盖整图（p.20；C 级）。
• 恢复负环从 p.34 开始，p.33 明确声明后续不考（B 级）。

附录

A1 多个强连通分量怎么办（非讲义内容）

p.20 提问的关键是源点可达性。可逐个 SCC 运行 Bellman–Ford，因为每个有向环必完整落在一个 SCC 内；总松弛量不超过顶点数乘边数的量级。另一办法增加连接所有顶点的零权超级源，或用等价的全零距离初始化，再做足够轮数。后者是在问“整张图有无负环”，不是计算某个原源点的最短距离。原讲义只抛出多分量问题，这里是对该问题的补充回答。

回到正文：检测范围

来源与证据

• 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

• 原件：T10-负环检测-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

• 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

• 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

• 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

• 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。