Bellman–FordBellman–Ford

重复松弛全部边，逐步允许更长的最短路径。

核心约束: 第 i 轮后，边数至多 i 的最短路径已纳入保证；原地松弛可能传播更长路径。
适用问题: 带负权边的单源最短路与可达负环检测。
边界与取舍: 存在可达负环时，部分最短距离没有有限解。

时间与空间#

V 为顶点数，E 为边数；逐轮扫描所有边。

时间复杂度: $O(VE+V)$
辅助空间: $O(V)$ ，保存距离与前驱

允许负边。最多 V−1 轮松弛并再检查一轮；若从源点可达负环，受其影响的目标没有有限最短路。提前结束不改变最坏界；不能把队列优化经验当作线性保证。

基础原理参考资料

Boost.Graph 1.85 · Bellman–Ford松弛步骤、负环检查和 O(VE) 主项。