bellman-ford

1 算法背景与核心直觉

在单源最短路问题中，当图上存在负权边（甚至可能包含负权环）时，基于贪心的 dijkstra 算法便不再适用。

Bellman-Ford 算法直接基于动态规划与边的反复松弛，不仅能够正确处理负权边，还能有效检测图中是否存在从源点可达的负权环。

2 核心定理与证明

定理1： 最短路上的点数与边数界限

在一个无负环的图 $G$ 上，从源点 $s$ 到任意可达点 $v$ 的最短路所经过的：

1. 点数不超过 $n$；
2. 边数不超过 $n - 1$。

证明（反证法）：

假设最短路径经过了超过 $n$ 个点，由于图上总共只有 $n$ 个顶点，根据抽屉原理（鸽巢原理），这条路径上必然至少有一个顶点重复出现，设该点为 $b$。

则整条路径可以表示为：

在路径中包含了一个起点与终点皆为 $b$ 的回路（圈）。

• 因为图 $G$ 中不存在负环，所以该回路的权值和必为非负值（$\geqslant 0$）。
• 如果我们将这个回路直接从路径中删去，得到新路径 $s \to \cdots \to b \to d \to \cdots \to v$：
  • 新路径的权值和必 $\leqslant$ 原路径的权值和；
  • 这与“原路径是最短路径且必须包含该回路”的前提矛盾！

因此，最短路径上一定不包含任何环，即必然是一条简单路径。 包含 $k \leqslant n$ 个点的简单链，其所包含的边数最多为 $n - 1$ 条。证毕。

3 松弛操作的定义

两个点 $u, v$ 的边 $(u, v)$，若发现通过 $u$ 到达 $v$ 比当前记录的 $dis(v)$ 更优，则进行更新：

4 算法核心过程与图解

Bellman-Ford 算法的核心在于：按轮次对图中的所有边进行整体松弛。

4.1 轮次演进不变量

设源点为 $s$，初始时令 $dis(s) = 0$，其余所有点 $dis(i) = \infty$。

核心归纳不变量：

在第 $k$ 轮全局边松弛结束后，$dis(v)$ 的值至多等于“从源点 $s$ 到 $v$ 且经过边数不超过 $k$ 条的最短路径长度”。

• 初始（$k=0$）：只有经过 $0$ 条边的源点自身距离为 $0$，其余不可达，不变量成立。
• 第 $1$ 轮（$k=1$）：枚举所有边，源点的一度邻居被松弛，得到了最多经过 $1$ 条边的最短距离。
• 第 $k$ 轮：任何最多经过 $k$ 条边的最短路径，其最后一步一定形如一条边 $(u, v)$，且前缀路径最多经过 $k-1$ 条边。由归纳假设，$dis(u)$ 在前 $k-1$ 轮已经达到最优，因此本轮松弛必然能算出不超过 $k$ 条边的最优 $dis(v)$。

4.2 为什么只需要 $n-1$ 轮？

根据定理1，在无负环的图上，任何点之间的最短路最多只包含 $n-1$ 条边。 因此，进行 $n-1$ 轮全边松弛之后，所有点的最终最短路都必然已经全部计算完成！

若在第 $k$（$k < n-1$）轮中没有发生任何松弛操作，说明所有距离已经收敛，可以提前跳出循环。

5 负环判定原理

如果在完成了 $n-1$ 轮松弛后，我们再进行第 $n$ 轮松弛：

• 如果此时仍然存在某条边 $(u, v)$ 满足 $dis(u) + w(u, v) < dis(v)$；
• 这说明存在一条能让距离更小的路径，其包含的边数至少为 $n$ 条；
• 边数 $\geqslant n$ 意味着该路径至少经过了 $n+1$ 个顶点，根据抽屉原理必定存在环，且绕这个环能让总距离变小——这证明图中必然存在从源点可达的负权环！

6 算法步骤总结

1. 初始化：$dis(s) = 0$，其余点 $dis = \infty$。
2. 进行至多 $n-1$ 轮循环：
   • 遍历图中的所有 $m$ 条边 $(u, v, w)$；
   • 若 $dis(u) \neq \infty$ 且 $dis(u) + w < dis(v)$，则更新 $dis(v) = dis(u) + w$；
   • 若本轮未发生任何松弛，提前退出。
3. 再遍历一次所有边：
   • 若仍能成功松弛，报告存在负环。
   • 否则输出最短路数组 $dis$。

7 模板代码

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

#include <algorithm>
#include <iostream>
#include <vector>

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

struct Edge {
    int u, v;
    long long w;
};

// 点编号为 1..n；返回 true 表示成功求得最短路，false 表示存在从源点可达的负环
bool bellman_ford(int n, const std::vector<Edge>& edges, int s, std::vector<long long>& dis) {
    dis.assign(n + 1, INF);
    dis[s] = 0;

    // 运行至多 n - 1 轮松弛
    for (int round = 1; round <= n - 1; ++round) {
        bool changed = false;
        for (const auto& e : edges) {
            if (dis[e.u] == INF) continue; // 源点尚不可达，不能拿 INF 参与相加
            if (dis[e.u] + e.w < dis[e.v]) {
                dis[e.v] = dis[e.u] + e.w;
                changed = true;
            }
        }
        // 如果某一轮没有发生任何松弛，说明所有最短路已经确定，可以提前退出
        if (!changed) break;
    }

    // 第 n 轮检测负环：若还能继续松弛，说明存在负环
    for (const auto& e : edges) {
        if (dis[e.u] == INF) continue;
        if (dis[e.u] + e.w < dis[e.v]) {
            return false; // 存在从 s 可达的负环
        }
    }
    return true;
}

8 复杂度与对比

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

• 时间复杂度：最坏情况下进行 $n$ 轮松弛，每轮遍历全部 $m$ 条边，时间复杂度为稳定 $O(nm)$。
• 空间复杂度：只需要存边数组和 $dis$ 数组，空间复杂度为 $O(n + m)$。

若要对 Bellman-Ford 的每轮盲目扫描进行常数优化，只让距离变小的点去通知邻居，则演化出队列优化的版本：spfa。 更多负环的判定方法（点更新次数、DFS 版负环判定等），请参见章节：负环。

9 相关题解

暂无相关题解