c++ Bellman-Ford算法的具体实现

前言

Bellman-Ford 算法解决的是单源最短路径问题，与 Dijkstra 的区别在于：它允许边权为负。代价是时间复杂度 O(V·E)，比 Dijkstra 的 O(E log V) 慢，但换来两个能力——处理负权边，以及检测负权环（negative cycle）。

最常见的误解是「有负权边就一定不能用 Dijkstra」。准确说法是：Dijkstra 要求所有边权非负；只要存在一条负权边，Dijkstra 的正确性证明就不再成立，可能给出错误结果。另一个误解是「Bellman-Ford 跑完就能得到最短路径」——如果从源点可达的负权环存在，最短路径没有下界，算法必须报告这一点，而不是返回一组数字。

本文讲松弛（relaxation）的本质、为什么是 V-1 轮、如何检测负权环、如何还原路径，并给出完整实现。代码以 C++17 编写，未在本机编译执行。

一、松弛：最短路径的基本操作

设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]

这个描述与具体实现无关：可以用边列表、邻接表或邻接矩阵，只要「每条边都被松弛一次」即可。边列表最直观，也最适合需要检测负权环的场景。

二、完整实现

// 适用于 C++17
#include <limits>
#include <vector>
#include <cstddef>

struct Edge {
int from;
int to;
long long weight;
};

constexpr long long kInf = std::numeric_limits<long long>::max() / 4;

// 返回 false 表示存在从源点可达的负权环
bool bellman_ford(int n, int src,
const std::vector<Edge>& edges,
std::vector<long long>& dist,
std::vector<int>& parent) {
dist.assign(static_cast<std::size_t>(n), kInf);
parent.assign(static_cast<std::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从终点往回走，就能还原一条最短路径：

// 适用于 C++17
#include <algorithm>
#include <vector>
#include <stdexcept>

std::vector<int> build_path(int src, int dst, const std::vector<int>& parent) {
std::vector<int> 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判断，负权边会让合法距离为负。

四、对比与工程注意事项

SPFA 是 Bellman-Ford 的队列优化：只有被更新的顶点才需要把它的出边重新松弛。它在随机图上通常快很多，但最坏情况仍是 O(V·E)，且存在被特意构造的图让它退化。工程代码若需要稳定上界，用 Bellman-Ford 或 Johnson 算法；竞赛里 SPFA 常见，但要清楚它没有优于 Bellman-Ford 的最坏复杂度。

Dijkstra 不能用负权边的原因可以用一个反例说明：s -> a权 2，s -> b权 5，b -> a权 -10。Dijkstra 先确定a的最短距离为 2 并「锁定」，但实际最短路径是s -> b -> a，长度 -5。锁定后不再更新，结果就错了。

优化与工程注意

• 
  
• 边列表只存一次：无向图要把每条边拆成两条有向边，负权无向图几乎必然含负权环（来回走一次就变短），使用前要想清楚语义。
• 
  
• 稀疏图用邻接表：边列表每轮都要遍历全部 E 条边，邻接表可以只遍历出边；但负权环检测仍需能枚举所有边。
• 
  
• Johnson 算法：所有边权可能为负时，先用 Bellman-Ford 求势能，把边权重映射为非负，再对每个源点跑 Dijkstra，适合「多源最短路」。
• 
  
• 数值类型：距离用long long，不要用int；路径长度可能超过int范围。边权若可能达到1e18，long long的加法也会溢出，需要更宽的类型或提前判断。
• 
  

常见坑点

• 
  
• ❌ 只跑 V-2 轮，认为最后一轮不重要。
• 
  

✅ 无负权环时最短路径最多 V-1 条边，必须跑满 V-1 轮（除非提前无更新）。

• 
  
• ❌ 用LLONG_MAX作无穷大，直接做dist[u] + w。
• 
  

✅ 用较小的哨兵值（如LLONG_MAX / 4），并在松弛前跳过不可达顶点。

• 
  
• ❌ 检测到负权环后仍然还原路径。
• 
  

✅ 先确认算法返回true，再沿parent回溯；或给回溯加步数上限。

• 
  
• ❌ 认为「图里有负权环」就一定返回失败。
• 
  

✅ 只有从源点可达的负权环才影响单源最短路；不可达的环不影响结果。

• 
  
• ❌ 对无向图直接套用负权边。
• 
  

✅ 无向负权边等价于负权环（一条边来回走），语义上通常不成立。

• 
  
• ❌ 用int存距离，长路径溢出。
• 
  

✅ 用long long，并评估边权量级；必要时用更宽类型。

• 
  
• ❌ 把 Dijkstra 用在含负权边的图上，只因为「测试用例碰巧对了」。
• 
  

✅ 有负权边就用 Bellman-Ford 或 Johnson；正确性不能靠样例覆盖。

• 
  
• ❌ 每轮都完整遍历，不做提前终止。
• 
  

✅ 记录本轮是否有更新，无更新即跳出。

总结

Bellman-Ford 的价值不在于快，而在于「在负权图上仍然正确，并且能告诉你图里有没有负权环」。把 V-1 轮的理由、第 V 轮检测的原理、以及哨兵值的溢出风险讲清楚，这个算法就不会再写成「跑几轮看看」。实际工程中，若图很大且边权非负，仍应优先 Dijkstra；只有在负权或需要环检测时，才付出 O(V·E) 的代价。