我的算法书 - Bellman-Ford 最短路

一句话算法

Bellman-Ford 反复松弛所有边；没有负环时，最短路最多经过 $n-1$ 条边。

问题模型

给定一张有向带权图，边权可以为负数。要求从源点 s 到所有点的最短距离，并判断从 s 可达的部分是否存在负环。

如果有负环可以从 s 到达，那么某些最短路可以无限变小，最短距离没有定义。

核心直觉

一条不含环的简单路径最多经过 $n-1$ 条边。

第 1 轮松弛后，可以得到“最多经过 1 条边”的最短路。

第 2 轮松弛后，可以得到“最多经过 2 条边”的最短路。

依此类推，第 n-1 轮后，所有简单最短路都已经被考虑到。

如果第 n 轮还能继续变小，说明存在可达负环。

松弛操作

对一条边 u -> v，边权为 w：

cpp

        1
2
3

        if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

这表示：如果先到 u，再走这条边去 v 更短，就更新 v 的距离。

算法步骤

初始化所有距离为 INF，令 dist[source] = 0。
重复 n-1 轮：
- 枚举所有边；
- 尝试用这条边进行松弛。
再枚举一次所有边：
- 如果还能松弛，说明存在从源点可达的负环。
否则 dist 就是最短路答案。

算法证明

核心不变量：第 k 轮松弛结束后，dist[v] 至多等于从源点到 v、最多经过 k 条边的最短路径长度。

初始时 k=0，只有源点距离为 0，其它点不可达，不变量成立。

假设第 k-1 轮后不变量成立。第 k 轮枚举所有边 u -> v，如果一条最多 k 条边的最短路径最后一条边是 u -> v，那么它的前缀是一条到 u、最多 k-1 条边的路径。根据归纳假设，dist[u] 已经不大于这个前缀长度，因此本轮可以把 dist[v] 更新到正确值。

没有负环时，最短路可以取为简单路径，最多经过 n-1 条边。因此 n-1 轮后答案正确。

如果第 n 轮还能松弛，说明存在一条更短的路径使用了至少 n 条边。路径中必然有重复点，形成一个环；这个环能让路径变短，所以是负环。

复杂度分析

设点数为 $n$ ，边数为 $m$ 。

时间复杂度： $O(nm)$ 。
空间复杂度： $O(n+m)$ 。

Bellman-Ford 适合需要负边权、负环判断，且数据规模不大的场景。

代码实现

输入格式：

n m source
u1 v1 w1
...
um vm wm

输出从源点到每个点的最短距离；若存在可达负环，输出 Negative cycle。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

        #include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, source;
    cin >> n >> m >> source;

    vector<Edge> edges;
    edges.reserve(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    vector<long long> dist(n + 1, INF);
    dist[source] = 0;

    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (const auto &edge : edges) {
            if (dist[edge.from] == INF) continue;
            if (dist[edge.to] > dist[edge.from] + edge.weight) {
                dist[edge.to] = dist[edge.from] + edge.weight;
                changed = true;
            }
        }
        if (!changed) break;
    }

    bool has_negative_cycle = false;
    for (const auto &edge : edges) {
        if (dist[edge.from] == INF) continue;
        if (dist[edge.to] > dist[edge.from] + edge.weight) {
            has_negative_cycle = true;
            break;
        }
    }

    if (has_negative_cycle) {
        cout << "Negative cycle\n";
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        if (dist[i] == INF) cout << "INF";
        else cout << dist[i];
    }
    cout << '\n';

    return 0;
}

测试用例

输入：

输出：

0 2 7 4 -2

应用分类详解

Bellman-Ford 的本质是用边数逐层扩展最短路。它适合处理负边权和负环判断。

一、含负权边的单源最短路

典型模式： 图中有负边，但没有负环。

识别信号： 出现“边权可能为负”“优惠/收益抵消代价”。

核心建模： 用 n-1 轮松弛覆盖所有简单路径。

二、负环检测

典型模式： 判断是否可以通过循环无限降低代价。

识别信号： 出现“是否存在负环”“是否能无限获利”。

核心建模： 第 n 轮仍能松弛，则存在可达负环。

三、差分约束

典型模式： 约束形如 x[v] <= x[u] + w。

识别信号： 出现多个不等式约束，要求判断是否有解。

核心建模： 把约束转成边 u -> v，用最短路或负环判断可行性。

经典例题

1. 单源最短路负权模板题

重点练习边表存图和 n-1 轮松弛。

2. 负环判断题

重点理解第 n 轮仍可松弛的含义。

3. 差分约束系统

把不等式转成图上的边，用 Bellman-Ford 判断是否有负环。