bellman-ford算法可检测有向图中是否存在负权环：先对所有边松弛v−1轮，再执行第v轮，若任一边仍可松弛，则存在负权环。
用 Bellman-Ford 判断负权环最直接
Bellman-Ford 是唯一能在有向图中可靠检测负权环的通用算法，前提是图连通性可控——它不要求从源点能到达所有点，但若只关心“图中是否存在负权环”，必须让松弛操作覆盖所有边，并运行 V-1 轮（V 为顶点数）。第 V 轮再检查是否还能松弛：只要任意一条边 dist[u] + w 成立，就说明存在负权环。
注意：不能只从某个点（如 0）开始跑标准 Bellman-Ford 就下结论。如果图不连通，负权环可能在其他连通分量里被漏掉。
- 初始化
dist[i]全为 0（不是INT_MAX），这是关键技巧：等价于加入一个虚拟源点，向所有点连 0 权边，确保能探测所有潜在负环 - 执行
V轮松弛（前V-1轮正常，第V轮纯检测） - 若第
V轮中任一边可更新，则存在负权环
SPFA 的优化版本容易误判
SPFA（队列优化的 Bellman-Ford）理论上也能检测负权环，但实际使用中极易因实现细节出错：
- 仅当节点入队次数 ≥
V时才判定负环，但需确保每个节点初始都入队一次（否则孤立负环分量无法触发） - 若用
vector<bool> inq</bool>控制入队，忘记重置或漏处理多连通分量，会漏检 - SPFA 最坏复杂度退化为
O(VE)，且某些 OJ 数据会卡死它；而朴素 Bellman-Ford 的O(VE)更稳定、更易 debug
除非明确要求提速且图稀疏、负环大概率靠近起点，否则别用 SPFA 替代标准 Bellman-Ford 做存在性判断。
用 Floyd-Warshall 检测要小心自环逻辑
Floyd-Warshall 可以检测负权环，但它判断依据是：运行结束后，若存在某个点 i 满足 dist[i][i] ，则说明存在经过 <code>i 的负权环。这看起来简洁，但有几个硬伤：
- 必须初始化
dist[i][i] = 0，不能设为INF，否则自环永远不更新 - 算法默认假设图是完全连通的（用
INF表示不可达），但若两点间无路径，dist[i][j]保持INF，不影响判断；真正要注意的是：中间点k必须按顺序枚举，且三重循环不能提前 break - 时间复杂度
O(V³)，比 Bellman-Ford 的O(VE)高得多，仅适合V ≤ 500的场景
它更适合“全源最短路+顺便查环”，而不是专为负环检测设计。
实际编码时最容易踩的初始化坑
三种算法都败在初始化上，尤其是初学者常犯的错：
- Bellman-Ford 中把
dist初始化为INT_MAX，然后只从 0 开始松弛 → 漏掉其他连通分量里的负环；正确做法是全设为 0 - Floyd 中把对角线
dist[i][i]设成INF或未初始化，导致dist[i][i]永远不更新，即使有负自环也判不出 - 读入边时没处理重边，保留最大/最小权重错误（负环检测必须保留**最小权重**的那条边，因为更小的权更容易触发负环条件）
负权环检测本质是“能否无限降低路径代价”，所有算法都围绕这个收敛性做文章。真正难的不是写对算法，而是确保图建模完整、初始化语义清晰、边界覆盖全面。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
