本课时有配套视频讲解，购买后即可观看（永久有效）

Bellman-Ford求单源最短路径

一、课上练习

编程练习

负环(BellmanFord)：L49986

二、知识总结

✨ 核心思想

Bellman-Ford 算法用于求解含负权边的单源最短路径问题。与 Dijkstra 不同，它不要求边权非负，并且能够检测负权环（负环）。

核心思想：对所有边进行 $V-1$ 轮松弛。第 $k$ 轮松弛后，保证所有经过不超过 $k$ 条边的最短路径被正确计算。由于最短路径最多经过 $V-1$ 条边（不含环）， $V-1$ 轮后所有最短路径都被求出。

✨ 算法原理

初始化：dist[s] = 0，其余 dist[v] = ∞。
松弛 $V-1$ 轮：对每一轮，遍历所有边 $(u, v, w)$ $(u, v, w)$ ，执行松弛：
```
if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
```
检测负环：第 $V$ 轮再次遍历所有边，如果仍有边可以被松弛，则说明图中存在从源点可达的负权环。

为什么 $V-1$ 轮就够了？

最短路径不包含环（正环绕了白绕，负环则无最短路）。不含环的路径最多经过 $V-1$ 条边。第 $i$ 轮松弛保证了"经过 $\leq i$ 条边的最短路径"被正确计算。因此 $V-1$ 轮后，所有最短路径都被计算完毕。

什么是负权环？

如果图中存在一个环，环上所有边权之和为负，那么可以无限走这个环来不断减小路径长度，此时最短路径不存在（为 $-\infty$ ）。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 10005;
5const int MAXM = 50005;
6const long long INF = 1e18;
7
8struct Edge {
9    int u, v;
10    long long w;
11};
12
13Edge edges[MAXM]; // 边集数组
14long long dist[MAXN];
15int n, m, s;
16
17bool bellmanFord(int s) {
18    // 初始化
19    for (int i = 1; i <= n; i++) dist[i] = INF;
20    dist[s] = 0;
21
22    // 进行 n-1 轮松弛
23    for (int i = 1; i <= n - 1; i++) {
24        bool updated = false; // 优化：本轮无更新则提前结束
25        for (int j = 0; j < m; j++) {
26            int u = edges[j].u, v = edges[j].v;
27            long long w = edges[j].w;
28            if (dist[u] != INF && dist[u] + w < dist[v]) {
29                dist[v] = dist[u] + w;
30                updated = true;
31            }
32        }
33        if (!updated) break; // 提前收敛
34    }
35
36    // 第 n 轮检测负环
37    for (int j = 0; j < m; j++) {
38        int u = edges[j].u, v = edges[j].v;
39        long long w = edges[j].w;
40        if (dist[u] != INF && dist[u] + w < dist[v]) {
41            return false; // 存在负环
42        }
43    }
44
45    return true; // 无负环
46}
47
48int main() {
49    ios::sync_with_stdio(false);
50    cin.tie(nullptr);
51
52    cin >> n >> m >> s;
53    for (int i = 0; i < m; i++) {
54        cin >> edges[i].u >> edges[i].v >> edges[i].w;
55    }
56
57    if (bellmanFord(s)) {
58        for (int i = 1; i <= n; i++) {
59            if (dist[i] == INF)
60                cout << "unreachable";
61            else
62                cout << dist[i];
63            if (i < n) cout << " ";
64        }
65        cout << endl;
66    } else {
67        cout << "NEGATIVE CYCLE" << endl;
68    }
69
70    return 0;
71}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 10005;
5const int MAXM = 50005;
6const long long INF = 1e18;
7
8struct Edge { int u, v; long long w; };
9
10Edge edges[MAXM];
11long long dist[MAXN];
12int pre[MAXN]; // 前驱节点
13int n, m;
14
15// 找到负环上的一个节点，并输出负环
16void findNegativeCycle() {
17    for (int i = 1; i <= n; i++) dist[i] = 0; // 全部初始化为0
18    fill(pre, pre + n + 1, -1);
19
20    int lastUpdated = -1;
21    for (int i = 1; i <= n; i++) {
22        lastUpdated = -1;
23        for (int j = 0; j < m; j++) {
24            int u = edges[j].u, v = edges[j].v;
25            long long w = edges[j].w;
26            if (dist[u] + w < dist[v]) {
27                dist[v] = dist[u] + w;
28                pre[v] = u;
29                lastUpdated = v;
30            }
31        }
32    }
33
34    if (lastUpdated == -1) {
35        cout << "NO NEGATIVE CYCLE" << endl;
36        return;
37    }
38
39    // 从lastUpdated回溯n步，确保在环上
40    int x = lastUpdated;
41    for (int i = 0; i < n; i++) x = pre[x];
42
43    // 输出环
44    cout << "Negative cycle: ";
45    int cur = x;
46    do {
47        cout << cur << " -> ";
48        cur = pre[cur];
49    } while (cur != x);
50    cout << x << endl;
51}

✨ 执行示例

图：4 个顶点，5 条边，源点 $s = 1$ 。

边：1→2(1), 1→3(4), 2→3(2), 3→4(1), 2→4(-5)

轮次	dist[2]	dist[3]	dist[4]	是否更新
初始	∞	∞	∞	-
第1轮	1	3	-4	是
第2轮	1	3	-4	否

第2轮无更新，提前结束。最短路径：

$1 \to 2$ ：1
$1 \to 3$ ：3（经过 1→2→3）
$1 \to 4$ ：-4（经过 1→2→4，因为有负权边 2→4=-5）

第4轮（检测负环）：无边可松弛，不存在负环。

✨ 解题步骤详解

判断是否需要 Bellman-Ford：
- 有负权边 → 必须用 Bellman-Ford（或 SPFA）。
- 需要检测负环 → 用 Bellman-Ford。
- 无负权边 → 优先用 Dijkstra（更快）。
选择存图方式：Bellman-Ford 遍历所有边，用边集数组最方便。
优化技巧：
- 提前终止：如果某轮没有任何更新，说明已收敛，可以 break。
- 限制最短路经过的边数：如果题目要求最多经过 $k$ 条边，只松弛 $k$ 轮。
判断负环的作用范围：
- 标准 Bellman-Ford 只能检测从源点可达的负环。
- 若要检测图中所有负环，将所有顶点初始距离设为 0。

✨ 常见错误

松弛轮数错误：应松弛 $V-1$ 轮（不是 $V$ 轮或 $E$ 轮）。
未检查 dist[u] != INF：源点不可达的顶点不应参与松弛，否则 INF + w 可能溢出。
无向图边数翻倍：无向图每条边存两次，边数组大小要 $2M$ 。
负环检测遗漏：忘记做第 $V$ 轮检测，导致在有负环时输出错误结果。
与 Dijkstra 混淆：Bellman-Ford 没有 vis 数组，不是贪心算法。
提前终止优化失效：只是优化常数，最坏情况仍需 $V-1$ 轮。

✨ 算法评价

指标	分析
时间复杂度	$O(VE)$ ， $V-1$ 轮，每轮遍历 $E$ 条边
空间复杂度	$O(V + E)$
适用场景	含负权边的图、需要检测负环
与 Dijkstra 对比	更慢但更通用，能处理负权边
与 SPFA 对比	SPFA 是其队列优化版本，通常更快

Bellman-Ford 是处理负权边的基础算法。虽然时间复杂度较高，但其思路简单、正确性容易证明，是理解 SPFA 等优化算法的前提。

三、课后练习

编程练习

信使：T1376