第n轮松弛仍能成功说明存在负权环，因为n个点的最短路径至多含n−1条边，若第n轮还能更新距离，则路径必含重复顶点即环，且该环权值为负，否则无法进一步缩短路径。
为什么第 n 轮松弛还能成功就说明有负权环
Bellman-Ford 的核心逻辑是：对一个含 n 个顶点的图，最多只需 n-1 轮松弛就能收敛到最短距离（前提是无负权环）。因为任意简单路径最多含 n-1 条边，多于这个数必然重复经过某个点——那就有环了。所以第 n 轮如果还能更新某点的 dist[v]，说明存在一条长度为 n 的路径比之前所有 n-1 条边的路径还短，只能是因为这条路径里绕了一个总权值为负的环。
检测负权环的标准写法是跑第 n 轮并观察是否更新
实际编码中，不需要额外 DFS 或回溯找环，只需在完成 n-1 轮主循环后，再做一次遍历所有边的松弛尝试：
- 若任意边
(u, v, w)满足dist[u] + w ，则存在负权环 - 此时
dist[v]的值已不可信，不能再用于后续计算 - 注意：必须用
dist[u]的当前值判断，不能加if (dist[u] == INF)就跳过——因为负权环可能从不可达状态“激活”新路径（尤其当图不连通时）
示例片段（伪代码风格）：
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
dist[src] = 0;
<p>for (int i = 0; i < n - 1; i++) {
for (auto [u, v, w] : edges) {
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}</p><p>bool has_negative_cycle = false;
for (auto [u, v, w] : edges) {
if (dist[u] != INF && dist[u] + w < dist[v]) {
has_negative_cycle = true;
break;
}
}</p>容易被忽略的边界：INF 值选太大或太小都会出问题
INF 不是越大越好，也不是随便设个 0x3f3f3f3f 就安全：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 若
INF过大（如LLONG_MAX），dist[u] + w可能溢出变成负数，导致错误触发更新 - 若
INF过小（如1e9），而边权范围是-1e5、边数又多，dist[u] + w可能仍小于INF，掩盖本该跳过的不可达点 - 推荐设为略大于最大可能最短路绝对值，例如：若
n ≤ 2000，边权 ∈[-1000, 1000]，则INF = 1e9是安全的；更通用可取INF = 1e18 / 2（留出加法余量）
检测到负权环后，想找出具体哪些点在环上怎么办
Bellman-Ford 本身不直接给出环的顶点序列，但可以基于第 n 轮更新的节点反向追踪：
- 记录每次成功更新
dist[v]时的前驱prev[v] = u - 检测到负环后，任取一个被第
n轮更新的v，沿prev走n步，用 set 或数组标记访问，首次重复出现的点就是环入口 - 更稳妥的做法是：再跑一遍 Bellman-Ford（不限轮数，直到稳定或迭代
n次），所有dist在最后几轮持续变小的点，都可到达负权环
这步不是必须的——多数场景下，知道“存在负权环”已足够拒绝后续最短路计算。硬要定位环，代价远高于检测本身。
