Bellman-Ford
Bellman-Ford 简介
Bellman-Ford 是解决 单源最短路 的经典算法。
它和 Dijkstra 最大的区别是：
- Dijkstra 不能处理负边
- Bellman-Ford 可以处理负边
- 并且 Bellman-Ford 还能判负环
这里的“负环”是指：从源点可达的某个环，环上边权和小于 0。
如果存在这种环，那么最短路就不存在，因为你可以在这个环上无限绕，使路径长度越来越小。
核心思想
设 dist[s]=0，其余点为正无穷。
然后进行若干轮“松弛”操作。
对于每条边 u -> v (w)，尝试更新：
[ dist[v] = \min(dist[v], dist[u] + w) ]
为什么这样做是对的？
因为：
- 第 1 轮后，可以得到“至多经过 1 条边”的最短路
- 第 2 轮后，可以得到“至多经过 2 条边”的最短路
- …
- 第
n-1轮后，可以得到“至多经过 n-1 条边”的最短路
一个不含环的最短路径，最多只会经过 n-1 条边，所以做 n-1 轮就够了。
为什么能判负环
如果做完 n-1 轮后，还能继续松弛某条边，说明存在一条“更优路径”需要经过至少 n 条边。
而一个含 n 条边的路径，在 n 个点的图中一定经过了重复点，也就是经过了环。
还能继续变优，说明这个环是负环。
因此：
- 做完
n-1轮后 - 再检查一遍所有边
- 若还能松弛，则存在 从源点可达的负环
适用场景
Bellman-Ford 常用于：
- 图中有负边
- 需要判断负环
- 某些题目建图后边数不算特别大
- 作为 SPFA 的理论基础
时间复杂度
设点数为 n，边数为 m`：
- 时间复杂度：O(nm)
- 空间复杂度：O(n + m)
这比堆优化 Dijkstra 的 O(m log n) 慢很多，所以在没有负边时一般不用它。
标准 OI 模板
这是最常见的竞赛写法：边集数组。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const long long INF = 1e18;
struct Edge {
int u, v;
long long w;
} e[10005];
long long dist[N];
bool bellman_ford(int n, int m, int s) {
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[s] = 0;
// 做 n-1 轮松弛
for (int i = 1; i <= n - 1; i++) {
bool updated = false;
for (int j = 1; j <= m; j++) {
int u = e[j].u, v = e[j].v;
long long w = e[j].w;
if (dist[u] != INF && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
updated = true;
}
}
if (!updated) break; // 提前结束优化
}
// 判负环：若还能松弛，则存在从 s 可达的负环
for (int j = 1; j <= m; j++) {
int u = e[j].u, v = e[j].v;
long long w = e[j].w;
if (dist[u] != INF && dist[v] > dist[u] + w) {
return false; // 有负环
}
}
return true; // 无负环
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
if (!bellman_ford(n, m, s)) {
cout << "Negative cycle\n";
} else {
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) cout << "INF ";
else cout << dist[i] << " ";
}
cout << '\n';
}
return 0;
}
模板细节解释
1. 为什么用边集而不是邻接表
Bellman-Ford 每一轮都要把 所有边扫一遍。
所以直接存边最方便：
struct Edge {
int u, v;
long long w;
};
每轮直接枚举 e[j] 即可。
2. 为什么要写 dist[u] != INF
if (dist[u] != INF && dist[v] > dist[u] + w)
这是为了防止：
u根本不可达INF + w参与运算导致错误
这是 Bellman-Ford 里必须写的判断。
3. 提前结束优化
bool updated = false;
...
if (!updated) break;
如果某一轮没有任何更新，说明最短路已经稳定了，后面不用再做。
这个优化在很多题里很有用。
一个简单例子
图：
1 -> 2 (2)1 -> 3 (5)2 -> 3 (-4)
源点 1。
初始：
dist[1]=0dist[2]=INFdist[3]=INF
第 1 轮松弛：
1 -> 2：dist[2]=21 -> 3：dist[3]=52 -> 3：dist[3]=min(5, 2+(-4))=-2
结果：
dist[1]=0dist[2]=2dist[3]=-2
这就是 Bellman-Ford 可以处理负边的体现。
和 Dijkstra 的对比
Dijkstra
- 不能有负边
- 速度快
- 常用于非负权图最短路
Bellman-Ford
- 能处理负边
- 能判负环
- 复杂度高
所以竞赛里一般是：
- 没有负边：优先 Dijkstra
- 有负边 / 需要判负环：Bellman-Ford 或 SPFA
Bellman-Ford 的一个常见变形
有时题目要求：
- 最多经过
k条边的最短路
这种题 Bellman-Ford 很适合做，因为“第 i 轮表示最多经过 i 条边”。
但这时要注意：
需要用一个 备份数组，避免同一轮中新更新的信息继续被用到。
模板如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const long long INF = 1e18;
struct Edge {
int u, v;
long long w;
} e[10005];
long long dist[N], backup[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k, s;
cin >> n >> m >> k >> s;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[s] = 0;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) backup[j] = dist[j];
for (int j = 1; j <= m; j++) {
int u = e[j].u, v = e[j].v;
long long w = e[j].w;
if (backup[u] != INF) {
dist[v] = min(dist[v], backup[u] + w);
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) cout << "INF ";
else cout << dist[i] << " ";
}
cout << '\n';
return 0;
}
竞赛里要注意的坑
1. INF 要开大
一般用：
const long long INF = 1e18;
不要随便开 1e9，边权和路径长度可能很大。
2. 判负环只判“从源点可达”的负环
因为代码里写了：
if (dist[u] != INF && ...)
所以只有从 s 能走到的负环才会被检测到。
这通常正是单源最短路题目要的。
如果题目要判图中 任意位置 是否存在负环，常见做法是：
- 建一个超级源点，向所有点连权值 0 的边
- 再跑 Bellman-Ford / SPFA 判负环
3. “恰好 k 条边” 和 “最多 k 条边” 不一样
Bellman-Ford 分层意义天然对应“最多”。
如果题目问“恰好”，需要额外设计状态。
一句话总结
Bellman-Ford 本质上是：
通过反复枚举所有边，逐步扩大允许经过的边数，从而求出单源最短路；同时可借助第 n 轮是否还能松弛来判断负环。