前言Bellman-Ford 算法解决的是单源最短路径问题与 Dijkstra 的区别在于它允许边权为负。代价是时间复杂度 O(V·E)比 Dijkstra 的 O(E log V) 慢但换来两个能力——处理负权边以及检测负权环negative cycle。最常见的误解是「有负权边就一定不能用 Dijkstra」。准确说法是Dijkstra 要求所有边权非负只要存在一条负权边Dijkstra 的正确性证明就不再成立可能给出错误结果。另一个误解是「Bellman-Ford 跑完就能得到最短路径」——如果从源点可达的负权环存在最短路径没有下界算法必须报告这一点而不是返回一组数字。本文讲松弛relaxation的本质、为什么是 V-1 轮、如何检测负权环、如何还原路径并给出完整实现。代码以 C17 编写未在本机编译执行。一、松弛最短路径的基本操作设dist[v]表示当前已知的从源点s到v的最短距离。对一条边(u, v, w)如果dist[u] w dist[v]就说明找到了一条更短的路径更新dist[v]。这个操作叫松弛。Bellman-Ford 的做法是把所有边松弛一遍称为一轮重复 V-1 轮。每一轮至少能让「边数不超过当前轮数」的最短路径确定下来。为什么是 V-1 轮在无负权环的图中任何最短路径都不会包含重复顶点含环的路径可以去掉环而不会更长因此最多有 V-1 条边。第 k 轮结束时所有「最多 k 条边」的最短路径都已确定V-1 轮后所有最短路径都确定。初始dist[s] 0其余为 INF重复 V-1 次对每条边 (u, v, w)若 dist[u] w dist[v]则更新 dist[v]这个描述与具体实现无关可以用边列表、邻接表或邻接矩阵只要「每条边都被松弛一次」即可。边列表最直观也最适合需要检测负权环的场景。二、完整实现// 适用于 C17#include limits#include vector#include cstddefstruct Edge {int from;int to;long long weight;};constexpr long long kInf std::numeric_limitslong long::max() / 4;// 返回 false 表示存在从源点可达的负权环bool bellman_ford(int n, int src,const std::vectorEdge edges,std::vectorlong long dist,std::vectorint parent) {dist.assign(static_caststd::size_t(n), kInf);parent.assign(static_caststd::size_t(n), -1);dist[src] 0;for (int round 0; round n - 1; round) {bool changed false;for (const Edge e : edges) {if (dist[e.from] kInf) {continue; // 源点还到不了松弛无意义}long long candidate dist[e.from] e.weight;if (candidate dist[e.to]) {dist[e.to] candidate;parent[e.to] e.from;changed true;}}if (!changed) {break; // 已无更新提前结束}}// 第 V 轮若还能松弛说明存在可达负权环for (const Edge e : edges) {if (dist[e.from] kInf) {continue;}if (dist[e.from] e.weight dist[e.to]) {return false;}}return true;}几处设计说明kInf取LLONG_MAX / 4而不是LLONG_MAX。松弛时会做dist[u] w如果dist[u]正好是LLONG_MAX加法立刻有符号溢出属于未定义行为undefined behavior, UB。用一个足够大的有限值并在松弛前跳过不可达顶点可以避免这个问题但若边权本身极大仍需评估kInf w是否可能溢出必要时改用__int128或提前判断。提前终止如果某一轮没有任何更新后续轮次也不会更新可以直接跳出。这对大多数图能显著减少轮数但不改变最坏复杂度。负权环检测放在 V-1 轮之后如果还能松弛说明存在一条「经过 V 条边仍能变短」的路径由抽屉原理路径中必有重复顶点即存在负权环。检测的是「从源点可达」的负权环。图里存在负权环但源点到不了算法仍会正常返回true这是符合单源最短路径语义的。三、路径还原与负权环的坑parent[v]记录的是「最后一次让dist[v]变小的前驱」。沿parent从终点往回走就能还原一条最短路径// 适用于 C17#include algorithm#include vector#include stdexceptstd::vectorint build_path(int src, int dst, const std::vectorint parent) {std::vectorint path;for (int v dst; v ! -1; v parent[v]) {path.push_back(v);if (path.size() parent.size()) { // 防御parent 成环throw std::runtime_error(parent chain contains a cycle);}}std::reverse(path.begin(), path.end());if (path.empty() || path.front() ! src) {throw std::runtime_error(destination is unreachable);}return path;}为什么要防御parent成环当存在可达负权环时环上的顶点会被反复更新parent指针可能互相指成一个环。此时如果先还原路径、后检查负权环for循环永远走不到-1。正确顺序是先跑完 Bellman-Ford 并确认返回true再还原路径或者像上面一样加步数上限。另一个细节dist[v] kInf表示不可达。不要用dist[v] LLONG_MAX判断因为你设的哨兵值可能不是它也不要用dist[v] 0判断负权边会让合法距离为负。四、对比与工程注意事项维度Bellman-FordDijkstraSPFA负权边支持不支持支持负权环检测支持不适用支持入队次数时间复杂度O(V·E)O(E log V)二叉堆平均较快最坏 O(V·E)实现难度低中中适用负权图、需要环检测非负权、稠密/稀疏均可竞赛中常见最坏无保证SPFA 是 Bellman-Ford 的队列优化只有被更新的顶点才需要把它的出边重新松弛。它在随机图上通常快很多但最坏情况仍是 O(V·E)且存在被特意构造的图让它退化。工程代码若需要稳定上界用 Bellman-Ford 或 Johnson 算法竞赛里 SPFA 常见但要清楚它没有优于 Bellman-Ford 的最坏复杂度。Dijkstra 不能用负权边的原因可以用一个反例说明s - a权 2s - b权 5b - a权 -10。Dijkstra 先确定a的最短距离为 2 并「锁定」但实际最短路径是s - b - a长度 -5。锁定后不再更新结果就错了。优化与工程注意边列表只存一次无向图要把每条边拆成两条有向边负权无向图几乎必然含负权环来回走一次就变短使用前要想清楚语义。稀疏图用邻接表边列表每轮都要遍历全部 E 条边邻接表可以只遍历出边但负权环检测仍需能枚举所有边。Johnson 算法所有边权可能为负时先用 Bellman-Ford 求势能把边权重映射为非负再对每个源点跑 Dijkstra适合「多源最短路」。数值类型距离用long long不要用int路径长度可能超过int范围。边权若可能达到1e18long long的加法也会溢出需要更宽的类型或提前判断。常见坑点❌ 只跑 V-2 轮认为最后一轮不重要。✅ 无负权环时最短路径最多 V-1 条边必须跑满 V-1 轮除非提前无更新。❌ 用LLONG_MAX作无穷大直接做dist[u] w。✅ 用较小的哨兵值如LLONG_MAX / 4并在松弛前跳过不可达顶点。❌ 检测到负权环后仍然还原路径。✅ 先确认算法返回true再沿parent回溯或给回溯加步数上限。❌ 认为「图里有负权环」就一定返回失败。✅ 只有从源点可达的负权环才影响单源最短路不可达的环不影响结果。❌ 对无向图直接套用负权边。✅ 无向负权边等价于负权环一条边来回走语义上通常不成立。❌ 用int存距离长路径溢出。✅ 用long long并评估边权量级必要时用更宽类型。❌ 把 Dijkstra 用在含负权边的图上只因为「测试用例碰巧对了」。✅ 有负权边就用 Bellman-Ford 或 Johnson正确性不能靠样例覆盖。❌ 每轮都完整遍历不做提前终止。✅ 记录本轮是否有更新无更新即跳出。总结要点结论解决问题单源最短路径允许负权边核心操作对每条边松弛重复 V-1 轮复杂度O(V·E)负权环检测第 V 轮仍能松弛即可达负权环路径还原沿parent回溯需防成环数值安全哨兵值留余量距离用long long对比Dijkstra 不支持负权SPFA 最坏同阶Bellman-Ford 的价值不在于快而在于「在负权图上仍然正确并且能告诉你图里有没有负权环」。把 V-1 轮的理由、第 V 轮检测的原理、以及哨兵值的溢出风险讲清楚这个算法就不会再写成「跑几轮看看」。实际工程中若图很大且边权非负仍应优先 Dijkstra只有在负权或需要环检测时才付出 O(V·E) 的代价。
前言Bellman-Ford 算法解决的是单源最短路径问题与 Dijkstra 的区别在于它允许边权为负。代价是时间复杂度 O(V·E)比 Dijkstra 的 O(E log V) 慢但换来两个能力——处理负权边以及检测负权环negative cycle。最常见的误解是「有负权边就一定不能用 Dijkstra」。准确说法是Dijkstra 要求所有边权非负只要存在一条负权边Dijkstra 的正确性证明就不再成立可能给出错误结果。另一个误解是「Bellman-Ford 跑完就能得到最短路径」——如果从源点可达的负权环存在最短路径没有下界算法必须报告这一点而不是返回一组数字。本文讲松弛relaxation的本质、为什么是 V-1 轮、如何检测负权环、如何还原路径并给出完整实现。代码以 C17 编写未在本机编译执行。一、松弛最短路径的基本操作设dist[v]表示当前已知的从源点s到v的最短距离。对一条边(u, v, w)如果dist[u] w dist[v]就说明找到了一条更短的路径更新dist[v]。这个操作叫松弛。Bellman-Ford 的做法是把所有边松弛一遍称为一轮重复 V-1 轮。每一轮至少能让「边数不超过当前轮数」的最短路径确定下来。为什么是 V-1 轮在无负权环的图中任何最短路径都不会包含重复顶点含环的路径可以去掉环而不会更长因此最多有 V-1 条边。第 k 轮结束时所有「最多 k 条边」的最短路径都已确定V-1 轮后所有最短路径都确定。初始dist[s] 0其余为 INF重复 V-1 次对每条边 (u, v, w)若 dist[u] w dist[v]则更新 dist[v]这个描述与具体实现无关可以用边列表、邻接表或邻接矩阵只要「每条边都被松弛一次」即可。边列表最直观也最适合需要检测负权环的场景。二、完整实现// 适用于 C17#include limits#include vector#include cstddefstruct Edge {int from;int to;long long weight;};constexpr long long kInf std::numeric_limitslong long::max() / 4;// 返回 false 表示存在从源点可达的负权环bool bellman_ford(int n, int src,const std::vectorEdge edges,std::vectorlong long dist,std::vectorint parent) {dist.assign(static_caststd::size_t(n), kInf);parent.assign(static_caststd::size_t(n), -1);dist[src] 0;for (int round 0; round n - 1; round) {bool changed false;for (const Edge e : edges) {if (dist[e.from] kInf) {continue; // 源点还到不了松弛无意义}long long candidate dist[e.from] e.weight;if (candidate dist[e.to]) {dist[e.to] candidate;parent[e.to] e.from;changed true;}}if (!changed) {break; // 已无更新提前结束}}// 第 V 轮若还能松弛说明存在可达负权环for (const Edge e : edges) {if (dist[e.from] kInf) {continue;}if (dist[e.from] e.weight dist[e.to]) {return false;}}return true;}几处设计说明kInf取LLONG_MAX / 4而不是LLONG_MAX。松弛时会做dist[u] w如果dist[u]正好是LLONG_MAX加法立刻有符号溢出属于未定义行为undefined behavior, UB。用一个足够大的有限值并在松弛前跳过不可达顶点可以避免这个问题但若边权本身极大仍需评估kInf w是否可能溢出必要时改用__int128或提前判断。提前终止如果某一轮没有任何更新后续轮次也不会更新可以直接跳出。这对大多数图能显著减少轮数但不改变最坏复杂度。负权环检测放在 V-1 轮之后如果还能松弛说明存在一条「经过 V 条边仍能变短」的路径由抽屉原理路径中必有重复顶点即存在负权环。检测的是「从源点可达」的负权环。图里存在负权环但源点到不了算法仍会正常返回true这是符合单源最短路径语义的。三、路径还原与负权环的坑parent[v]记录的是「最后一次让dist[v]变小的前驱」。沿parent从终点往回走就能还原一条最短路径// 适用于 C17#include algorithm#include vector#include stdexceptstd::vectorint build_path(int src, int dst, const std::vectorint parent) {std::vectorint path;for (int v dst; v ! -1; v parent[v]) {path.push_back(v);if (path.size() parent.size()) { // 防御parent 成环throw std::runtime_error(parent chain contains a cycle);}}std::reverse(path.begin(), path.end());if (path.empty() || path.front() ! src) {throw std::runtime_error(destination is unreachable);}return path;}为什么要防御parent成环当存在可达负权环时环上的顶点会被反复更新parent指针可能互相指成一个环。此时如果先还原路径、后检查负权环for循环永远走不到-1。正确顺序是先跑完 Bellman-Ford 并确认返回true再还原路径或者像上面一样加步数上限。另一个细节dist[v] kInf表示不可达。不要用dist[v] LLONG_MAX判断因为你设的哨兵值可能不是它也不要用dist[v] 0判断负权边会让合法距离为负。四、对比与工程注意事项维度Bellman-FordDijkstraSPFA负权边支持不支持支持负权环检测支持不适用支持入队次数时间复杂度O(V·E)O(E log V)二叉堆平均较快最坏 O(V·E)实现难度低中中适用负权图、需要环检测非负权、稠密/稀疏均可竞赛中常见最坏无保证SPFA 是 Bellman-Ford 的队列优化只有被更新的顶点才需要把它的出边重新松弛。它在随机图上通常快很多但最坏情况仍是 O(V·E)且存在被特意构造的图让它退化。工程代码若需要稳定上界用 Bellman-Ford 或 Johnson 算法竞赛里 SPFA 常见但要清楚它没有优于 Bellman-Ford 的最坏复杂度。Dijkstra 不能用负权边的原因可以用一个反例说明s - a权 2s - b权 5b - a权 -10。Dijkstra 先确定a的最短距离为 2 并「锁定」但实际最短路径是s - b - a长度 -5。锁定后不再更新结果就错了。优化与工程注意边列表只存一次无向图要把每条边拆成两条有向边负权无向图几乎必然含负权环来回走一次就变短使用前要想清楚语义。稀疏图用邻接表边列表每轮都要遍历全部 E 条边邻接表可以只遍历出边但负权环检测仍需能枚举所有边。Johnson 算法所有边权可能为负时先用 Bellman-Ford 求势能把边权重映射为非负再对每个源点跑 Dijkstra适合「多源最短路」。数值类型距离用long long不要用int路径长度可能超过int范围。边权若可能达到1e18long long的加法也会溢出需要更宽的类型或提前判断。常见坑点❌ 只跑 V-2 轮认为最后一轮不重要。✅ 无负权环时最短路径最多 V-1 条边必须跑满 V-1 轮除非提前无更新。❌ 用LLONG_MAX作无穷大直接做dist[u] w。✅ 用较小的哨兵值如LLONG_MAX / 4并在松弛前跳过不可达顶点。❌ 检测到负权环后仍然还原路径。✅ 先确认算法返回true再沿parent回溯或给回溯加步数上限。❌ 认为「图里有负权环」就一定返回失败。✅ 只有从源点可达的负权环才影响单源最短路不可达的环不影响结果。❌ 对无向图直接套用负权边。✅ 无向负权边等价于负权环一条边来回走语义上通常不成立。❌ 用int存距离长路径溢出。✅ 用long long并评估边权量级必要时用更宽类型。❌ 把 Dijkstra 用在含负权边的图上只因为「测试用例碰巧对了」。✅ 有负权边就用 Bellman-Ford 或 Johnson正确性不能靠样例覆盖。❌ 每轮都完整遍历不做提前终止。✅ 记录本轮是否有更新无更新即跳出。总结要点结论解决问题单源最短路径允许负权边核心操作对每条边松弛重复 V-1 轮复杂度O(V·E)负权环检测第 V 轮仍能松弛即可达负权环路径还原沿parent回溯需防成环数值安全哨兵值留余量距离用long long对比Dijkstra 不支持负权SPFA 最坏同阶Bellman-Ford 的价值不在于快而在于「在负权图上仍然正确并且能告诉你图里有没有负权环」。把 V-1 轮的理由、第 V 轮检测的原理、以及哨兵值的溢出风险讲清楚这个算法就不会再写成「跑几轮看看」。实际工程中若图很大且边权非负仍应优先 Dijkstra只有在负权或需要环检测时才付出 O(V·E) 的代价。
