学习目标

• 能复述教材 7.3 节中负权边使 Dijkstra 失效的反例；
• 能实现 Bellman-Ford 的 $n-1$ 轮全边松弛；
• 能用第 $n$ 轮是否仍能松弛检测从源点可达的负环；
• 能处理无穷大哨兵参与松弛时的溢出问题。

前置知识

先读第 7.4 节最短路径中的“负权边为何使 Dijkstra 失效”小节，并完成 Lab 07-E-16：Dijkstra 逐轮推演。本题进一步处理允许负权边的单源最短路，并检测从源点可达的负环。

为什么需要新算法

Dijkstra 把当前最小距离顶点标记为已确定，正确性依赖最短路径前缀的权值不超过整条路径；若尾段含负权边，这个不等式可能失效。教材中的反例如下：

0 → 1  权 1
0 → 2  权 2
2 → 1  权 -2

真实最短路 $d(0,1)=0$（走 0→2→1，$2+(-2)=0$），但 Dijkstra 第一轮就把 1 的估计值 $1$ 标记为最终距离。Bellman-Ford 不会提前把某个顶点永久确定，而是重复扫描全部边；完成第 $i$ 轮后，算法至少已经覆盖所有可由不超过 $i$ 条边构成的最短路径。

Bellman-Ford 算法

对边表 edges[0..m)，重复 $n-1$ 轮：

for i in 1..n-1:
    for each edge (u, v, w) in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            prev[v] = u

• 为什么 $n-1$ 轮够：不存在从源点可达的负环时，对每个具有有限最短距离的顶点，都能选出一条不重复顶点的最短路径；若路径含权值非负的回路，删去该回路不会使路径变长。这样的简单路径至多有 $n-1$ 条边。第 $i$ 轮结束时，所有能由不超过 $i$ 条边的最短路径到达的顶点都已得到正确距离。
• 负环检测：再做第 $n$ 轮，仍须先判断 dist[u] != INF；若仍有一条可达边能松弛，说明存在一条从源点可达的总权为负的闭路（负环），最短距离无下界，输出 NEGATIVE CYCLE。

输入格式

第一行三个整数 n m s：顶点数、有向边数、源点编号。

接下来 m 行，每行三个整数 u v w，表示 u -> v 的有向边，边权 w 可以为负。

输入保证：

• 1 <= n <= 1000；
• 0 <= m <= 3000；
• 0 <= u, v < n；
• 0 <= s < n；
• -10^4 <= w <= 10^4；
• 边权范围保证任何有限 dist 都在 long long 内。

输出格式

若存在从源点可达的负环，输出一行：

NEGATIVE CYCLE

否则输出两行：

第一行 n 个整数 dist[i]（不可达输出 -1）；

第二行 n 个整数 prev[i]（源点与不可达顶点输出 -1）。

样例输入 1（教材反例，含负边无负环）

4 5 0
0 1 1
0 2 2
2 1 -2
1 3 5
2 3 8

样例输出 1

0 0 2 5
-1 2 0 1

样例解释 1

$d(0,1)=0$ 来自 $0\to 2\to 1$（$2+(-2)=0$），前驱是 2。$d(0,3)=5$ 走 $0\to 2\to 1\to 3$（$2-2+5=5$）。这正是 Dijkstra 算错的那个图——负权边迫使路径先绕远再抄近路。

样例输入 2（含负环）

3 3 0
0 1 1
1 2 -3
2 1 1

样例输出 2

NEGATIVE CYCLE

样例解释 2

环 1→2→1 总权 $-3+1=-2<0$，从 0 可达。每绕一圈 0→1→2→1→2→… 到 2 的距离都再降 2，最短路径失去下界。

任务

1. 读入边表（按数组顺序存储，直接对边表反复松弛，不建邻接表）；
2. 初始化 dist[s]=0，其余无穷；
3. 松弛 $n-1$ 轮，维护 prev；
4. 第 $n$ 轮再扫一遍全部边：若仍能松弛，输出 NEGATIVE CYCLE；
5. 否则输出 dist 与 prev（无穷与源点输出 -1）。

正常、边界与错误情况

情况	预期行为
含负权但无负环	正确输出最短路
负环从源点不可达	不影响结果，不报负环（仅当松弛更新可达时触发）
负权自环	若 w<0 且从源点可达，即负环，必然触发检测
零权边	正常处理
n==1 且无边或无可达负环	输出 0 与 -1
n==1 且存在可达负权自环	输出 NEGATIVE CYCLE
松弛读无穷	必须先判断 dist[u] 有限，避免 INF + 负权 溢出

运行与评分

在本 Lab 目录执行：

make doctor
make run
make run CASE=001-sample
make score

未安装 Make 时，在仓库根目录执行：

pnpm lab:doctor -- labs/chapter-07/exercise/E-07-19-bellman-ford-negative
pnpm lab:run -- labs/chapter-07/exercise/E-07-19-bellman-ford-negative
pnpm lab:score -- labs/chapter-07/exercise/E-07-19-bellman-ford-negative

完成清单

• 全部测试用例通过；
• 松弛前判断 dist[u] 有限，INF 不参与 +w 运算；
• 第 $n$ 轮检测在完整 $n-1$ 轮之后进行；
• 只有"从源点可达"的负环才输出 NEGATIVE CYCLE；
• prev 在负环检测后不再更新（直接输出标记）。

解题思路

重复扫描全部边并进行松弛，最多执行 n-1 轮即可得到没有负环时的最短路。第 n 轮若仍能改进，则从源点可达负环；不可达部分的边不能触发负环判定。

复杂度分析

$n-1$ 轮 × 每轮 $m$ 条边 = $O(nm)$ 时间，$O(n+m)$ 空间。在边权非负且只需求单源最短路时，Dijkstra 的 $O((n+m)\log n)$ 通常更合适；允许负权边或需要检测源点可达的负环时，应选择 Bellman-Ford。

思考与复盘

1. 反例图中，Dijkstra 具体在哪一步出错？对应的证明步骤"前缀 ≤ 全长"在哪一步断裂？

查看参考答案

从 0 出发时，dist[1]=1、dist[2]=2，Dijkstra 会先确定顶点 1。随后处理 2→1(-2) 才发现距离应为 0，但 1 已被错误地确定。路径 0→2→1 的前缀长度是 2，反而大于全路径长度 0；负边正是在这里打破了证明所需的“前缀不超过全长”。

2. 不存在源点可达的负环时，为什么扫描全部边 $n-1$ 轮足以得到所有有限最短距离？一条含 $n$ 条边的走法为什么一定重复顶点，又为什么可以删去其中的回路？

查看参考答案

不存在源点可达的负环时，总能选择一条不重复顶点的最短路：若某条从源点出发的最短走法重复顶点，重复部分构成的回路权值不可能为负；删除它不会让路径变长。简单路径最多经过 n 个顶点，因此至多有 n-1 条边。若一条路径有 n 条边，就经过 n+1 次顶点访问，按抽屉原理必有顶点重复。

3. 若负环从源点不可达，为什么第 $n$ 轮检测不会误报？

查看参考答案

初始化后只有源点距离有限，松弛前又跳过 dist[u]==INF 的边。不可达负环中的所有顶点始终保持无穷，不会参与任何松弛，因此第 $n$ 轮不会因它而报告负环。

4. Bellman-Ford 与 Floyd 都能检测负环，检测方式分别是什么？各自更擅长哪种图？

查看参考答案

Bellman-Ford 在完成 n-1 轮后再扫一轮；从给定源点可达的边仍能松弛，就有可达负环。Floyd 完成三重循环后检查是否存在 d[i][i] < 0。前者适合单源、稀疏图，时间为 $O(nm)$；后者一次得到全源结果，适合顶点较少、稠密或本就需要多点对查询的图，时间为 $O(n^3)$。