精华推荐

Bellman-Ford与SPFA算法的正确性证明

YIZHIYANG初来乍到 2025-9-17 3:06:38 13 浏览 0 点赞 0 收藏

预备知识与符号约定

在开始证明之前，我们首先需要建立一套清晰的数学语言与符号体系。

图的表示：一个带权有向图被表示为 $G = (V, E)$ ，其中 $V$ 是顶点的集合， $E$ 是边的集合。图中顶点的数量记为 $|V|$ ，边的数量为 $|E|$ 。每条边 $(u, v) \in E$ 都有一个权重（cost），由函数 $w: E \to \mathbb{R}$ 定义。

路径与路径权重：一条从顶点 $v_0$ 到 $v_k$ 的路径 $p$ 是一个顶点序列 $\langle v_0, v_1, \dots, v_k \rangle$ ，其中对所有的 $i \in [1, k]$ ，边 $(v_{i-1}, v_i) \in E$ 。路径 $p$ 的权重是构成它所有边的权重之和：
$w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)$
最短路径权重：从顶点 $u$ 到顶点 $v$ 的最短路径权重 $\delta(u, v)$ 定义如下：
$$\delta(u, v) = \begin{cases} \min\{w(p) \mid u \xrightarrow{p} v\} & \text{如果存在从 } u \text{ 到 } v \text{ 的路径} \\ \infty & \text{否则} \end{cases} $$
若图中存在从 $u$ 可达的负权环路，且该环路位于某条从 $u$ 到 $v$ 的路径上，那么 $\delta(u, v) = -\infty$ 。
最短路径估计：在算法执行过程中，我们为每个顶点 $v \in V$ 维护一个最短路径的估计值，记为 $d[v]$ 。算法开始时，除了源点 $s$ 的估计值为 $0$ 外，所有其他顶点的估计值均为 $\infty$ 。
松弛操作 (Relaxation)：松弛是所有此类算法的核心操作。对于一条边 $(u, v) \in E$ ，松弛操作试图利用 $u$ 的当前最短路径估计值 $d[u]$ 来改善 $v$ 的估计值 $d[v]$ 。其过程如下：
```
if (d[v] > d[u] + w(u, v)) {
    d[v] = d[u] + w(u, v);
    // 可能还会更新 v 的前驱节点 pi[v] = u
}
```
松弛操作的本质是在问：“经过顶点 $u$ 到达顶点 $v$ 是否会比当前已知的到达 $v$ 的路径更短？”如果是，则更新 $d[v]$ 。

基于这些定义，我们可以提出几个最短路径所固有的基本性质：

上界性质 (Upper-Bound Property)：对于所有顶点 $v \in V$ ，我们始终有 $d[v] \geq \delta(s, v)$ 。这个性质在初始化后成立，并且在每次松弛操作后依然保持。因为 $d[v]$ 的更新只会在找到一条更短的、实际存在的路径时发生，所以它永远不会低估真正的最短路径。
三角不等式 (Triangle Inequality)：对于任意边 $(u, v) \in E$ ，我们有 $\delta(s, v) \leq \delta(s, u) + w(u, v)$ 。这是最短路径的内在属性，即从 $s$ 到 $v$ 的最短路径，不可能比“从 $s$ 到 $u$ 的最短路径，再沿着边 $(u, v)$ 走到 $v$ ”更长。

当算法终止，且所有 $d[v]$ 都收敛时，如果 $d[v] = \delta(s, v)$ 对所有 $v \in V$ 成立，那么算法就是正确的。

Bellman-Ford算法及其正确性证明

Bellman-Ford算法通过对图中的所有边进行 $|V|-1$ 轮迭代松弛来计算单源最短路径。其结构异常简洁，背后却蕴含着深刻的动态规划思想。

算法描述

初始化：对于图中所有顶点 $v \in V$ ： $d[v] \leftarrow \infty$ $d[s] \leftarrow 0$ （ $s$ 是源点）
迭代松弛：重复 $|V|-1$ 次：对于图中每条边 $(u, v) \in E$ ：执行松弛操作：if (d[v] > d[u] + w(u, v)) d[v] = d[u] + w(u, v);
负权环路检测：对于图中每条边 $(u, v) \in E$ ：如果 d[v] > d[u] + w(u, v) 成立，则报告图中存在负权环路。

正确性证明

Bellman-Ford算法的正确性证明分为两个部分：首先证明在没有负权环路的情况下，算法能正确计算出所有最短路径；其次证明算法能检测出负权环路的存在。

1. 最短路径计算的正确性

我们将通过数学归纳法来证明，在没有负权环路的前提下，经过 $|V|-1$ 轮松弛后，对所有顶点 $v \in V$ ，都有 $d[v] = \delta(s, v)$ 。

我们引入一个关键的辅助定义：令 $d_i[v]$ 表示在完成第 $i$ 轮对所有边的松弛操作后， $v$ 的最短路径估计值。

引理：在第 $i$ 轮松弛之后，对于任意顶点 $v$ ， $d_i[v]$ 是从源点 $s$ 到 $v$ 的、边数至多为 $i$ 的所有路径中，权重最小的路径的权重。

证明：我们对轮数 $i$ 进行归纳。

基础情况 (Base Case), i = 0: 在第 0 轮（即初始化后）， $d_0[s] = 0$ ， $d_0[v] = \infty$ (对于 $v \neq s$ )。从 $s$ 到 $s$ 的、边数至多为 0 的路径只有一条空路径，权重为 0。因此 $d_0[s]$ 正确。对于任何 $v \neq s$ ，不存在从 $s$ 到 $v$ 的、边数为 0 的路径，其最短路径权重应为 $\infty$ 。因此 $d_0[v]$ 也正确。故引理在 $i=0$ 时成立。
归纳步骤 (Inductive Step): 假设在第 $i-1$ 轮后，引理成立，即 $d_{i-1}[v]$ 是从 $s$ 到 $v$ 的、边数至多为 $i-1$ 的最短路径权重。我们需要证明在第 $i$ 轮后， $d_i[v]$ 是从 $s$ 到 $v$ 的、边数至多为 $i$ 的最短路径权重。

考虑一条从 $s$ 到 $v$ 的、边数至多为 $i$ 的最短路径 $p$ 。该路径有两种可能：
1. 路径 $p$ 的边数至多为 $i-1$ 。在这种情况下，根据归纳假设，其权重已经不小于 $d_{i-1}[v]$ 。在第 $i$ 轮松弛中， $d[v]$ 的值只会减小或不变，所以 $d_i[v] \leq d_{i-1}[v]$ 。因此， $d_i[v]$ 仍然是这条路径权重的下界。
2. 路径 $p$ 的边数恰好为 $i$ 。设路径为 $s \to \dots \to u \to v$ ，其中 $s \to \dots \to u$ 子路径的边数为 $i-1$ 。这条子路径必定是从 $s$ 到 $u$ 的、边数至多为 $i-1$ 的最短路径。根据归纳假设， $d_{i-1}[u]$ 就是这条子路径的权重。在第 $i$ 轮松弛中，算法会遍历到边 $(u, v)$ 并执行松弛操作。此时，会进行比较： $d_i[v] \le d_{i-1}[u] + w(u, v)$ 这表明， $d_i[v]$ 的值不会超过这条 $s \to \dots \to u \to v$ 路径的权重。
综合以上两点，在第 $i$ 轮迭代之后， $d_i[v]$ 的值不会超过任何一条从 $s$ 到 $v$ 的、边数至多为 $i$ 的路径的权重。同时，根据上界性质， $d_i[v]$ 也不会低于真正的最短路径值。因此， $d_i[v]$ 恰好等于从 $s$ 到 $v$ 的、边数至多为 $i$ 的最短路径的权重。

归纳假设成立。

定理：若图 $G$ 不包含从源点 $s$ 可达的负权环路，则经过 $|V|-1$ 轮松弛后， $d[v] = \delta(s, v)$ 对所有 $v \in V$ 成立。

证明：在不包含负权环路的图中，任意两个顶点之间的最短路径必然是简单路径（不含重复顶点）。一条简单路径的边数最多为 $|V|-1$ 。根据我们刚刚证明的引理，在第 $|V|-1$ 轮松弛之后， $d_{|V|-1}[v]$ 的值等于从 $s$ 到 $v$ 的、边数至多为 $|V|-1$ 的所有路径中的最短路径权重。由于任何一条最短路径的边数都不可能超过 $|V|-1$ ，所以这个值就是真正的最短路径权重 $\delta(s, v)$ 。即， $d_{|V|-1}[v] = \delta(s, v)$ 。算法正确。

2. 负权环路检测的正确性

定理：当且仅当图 $G$ 中存在从源点 $s$ 可达的负权环路时，在 $|V|-1$ 轮迭代之后，第 $|V|$ 轮迭代仍会发生松弛操作。

证明：

"如果" 部分 (Sufficient Condition)：假设图中没有从 $s$ 可达的负权环路。根据上一个定理，在 $|V|-1$ 轮迭代后，我们已经得到 $d[v] = \delta(s, v)$ 对于所有 $v \in V$ 成立。根据最短路径的三角不等式性质，对于任意边 $(u, v) \in E$ ，必然有 $\delta(s, v) \leq \delta(s, u) + w(u, v)$ 。代入 $d[v]$ 和 $d[u]$ ，我们得到 $d[v] \leq d[u] + w(u, v)$ 。这意味着在第 $|V|$ 轮迭代中，松弛条件 d[v] > d[u] + w(u, v) 永远不会被满足。因此，不会有任何成功的松弛操作。
"必要" 部分 (Necessary Condition)：假设图中存在一个从源点 $s$ 可达的负权环路 $C = \langle v_0, v_1, \dots, v_k \rangle$ ，其中 $v_0 = v_k$ 。该环路权重为 $\sum_{i=1}^{k} w(v_{i-1}, v_i) < 0$ 。我们用反证法。假设在第 $|V|$ 轮迭代中没有发生松弛操作。这意味着在第 $|V|-1$ 轮迭代结束后，对于图中所有边 $(u, v) \in E$ ，都满足 $d[v] \leq d[u] + w(u, v)$ 。将这个不等式应用于环路 $C$ 上的所有边：
$d[v_1] \le d[v_0] + w(v_0, v_1)$ $d[v_2] \le d[v_1] + w(v_1, v_2)$ $\dots$ $d[v_k] \le d[v_{k-1}] + w(v_{k-1}, v_k)$
将这 $k$ 个不等式相加，得到：
$$\sum_{i=1}^{k} d[v_i] \le \sum_{i=1}^{k} d[v_{i-1}] + \sum_{i=1}^{k} w(v_{i-1}, v_i) $$
由于 $v_0 = v_k$ ，不等式左右两边的 $\sum d[v]$ 项可以精确地消掉（因为 $\sum_{i=1}^{k} d[v_i] = \sum_{i=1}^{k} d[v_{i-1}]$ ）。这样我们就得到了：
$0 \le \sum_{i=1}^{k} w(v_{i-1}, v_i)$
这与 $C$ 是一个负权环路（即其权重和小于0）的假设相矛盾。因此，我们的初始假设（第 $|V|$ 轮没有松弛）是错误的。必然至少有一条环上的边的松弛条件会被满足，导致 $d$ 值继续下降。这意味着只要负权环路存在， $d$ 值理论上可以无限下降，而算法通过在第 $|V|$ 轮检查是否仍有松弛发生来捕捉到这一现象。

证毕。Bellman-Ford算法的正确性得到了完全的证明。

代码实现

下面是一个 Bellman-Ford 算法的 C++ 实现，用于解决一个典型的最短路问题。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 510, M = 10010;
const ll INF = 1e18; // 使用长整型以防权重和溢出

int n, m, k; // 点数，边数，要求的最短路径边数（可选）
ll d[N];     // d[i]存储从源点到i的最短距离
ll bak[N];   // 备份数组，防止串联更新

struct Edge {
    int u, v, w;
} e[M];

void bfd() {
    memset(d, 0x3f, sizeof d); // 初始化为无穷大
    d[1] = 0; // 源点为1

    // 进行 n-1 轮松弛
    for (int i = 0; i < n; ++i) {
        memcpy(bak, d, sizeof d); // 备份d数组，防止一轮内发生串联更新
        for (int j = 0; j < m; ++j) {
            int u = e[j].u, v = e[j].v, w = e[j].w;
            if (bak[u] != 0x3f3f3f3f3f3f3f3fLL) { // 仅当u可达时才松弛
                d[v] = min(d[v], bak[u] + w);
            }
        }
    }
}

// 负权环检测: 在n-1轮后再进行一轮
// 如果d[v] > d[u] + w，则存在负环
bool neg_cyc() {
    memcpy(bak, d, sizeof d);
    for (int j = 0; j < m; ++j) {
        int u = e[j].u, v = e[j].v, w = e[j].w;
        if (bak[u] != 0x3f3f3f3f3f3f3f3fLL) {
             if (d[v] > bak[u] + w) {
                return true;
             }
        }
    }
    return false;
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }

    bfd();

    // 通常如果距离大于某个阈值（比如INF/2），就认为不可达
    if (d[n] > INF / 2) {
        cout << "impossible" << endl;
    } else {
        if (neg_cyc()) {
             // 检查负环是否影响到目标点，这需要更复杂的判断
             // 但一般如果题目问是否存在负环，这样即可
             cout << "negative cycle detected" << endl;
        } else {
             cout << d[n] << endl;
        }
    }

    return 0;
}

代码解释：
- 使用结构体 Edge 存储所有边。
- bfd 函数执行 Bellman-Ford 算法的核心逻辑。外层循环执行 n 次（实际上 n-1 次就足够计算最短路，多一次用于检测）。
- bak 数组是 Bellman-Ford 算法实现中的一个关键细节。在每一轮松弛中，我们应该使用上一轮迭代结束时的 d 值来计算新的 d 值。如果在同一轮中直接更新 d 数组，可能会导致“串联更新”，即在一个循环内，用刚刚被更新过的 d[u] 去更新 d[v]，这相当于在一次迭代中走了多步。为了严格符合我们证明中的 $d_i$ 定义，需要一个备份。
复杂度分析：
- 时间复杂度： $O(|V| \cdot |E|)$ 。外层循环执行 $|V|-1$ 次（或 $|V|$ 次以检测负环），内层循环遍历所有 $|E|$ 条边。
- 空间复杂度： $O(|V| + |E|)$ 。用于存储距离数组和边列表。

SPFA算法及其正确性证明

SPFA（Shortest Path Faster Algorithm）观察到，Bellman-Ford算法在许多轮次中执行了大量“无效”的松弛操作。如果一个顶点 $u$ 的最短路径估计值 $d[u]$ 在一整轮中都没有发生变化，那么在下一轮中，从 $u$ 出发的所有边的松弛操作也必然是无效的。SPFA正是基于这一洞察，使用一个队列来维护那些 $d$ 值被“刚刚更新过”的顶点，只对这些顶点的出边进行松弛。

算法描述

初始化：
- 对于图中所有顶点 $v \in V$ ： $d[v] \leftarrow \infty$ 。
- $d[s] \leftarrow 0$ 。
- 创建一个队列 q，将源点 $s$ 入队。
- 用一个布尔数组 in_q 标记顶点是否在队列中，in_q[s] = true。
迭代处理：
- 当队列 q 不为空时：
  - 从队首取出一个顶点 $u$ ，in_q[u] = false。
  - 遍历所有从 $u$ $u$ 出发的边 $(u, v) \in E$ $(u, v) \in E$ ：
    - 执行松弛操作：if (d[v] > d[u] + w(u, v))
      - d[v] = d[u] + w(u, v)
      - 如果顶点 $v$ 不在队列 q 中，则将其入队，并设置 in_q[v] = true。

正确性证明

SPFA的正确性可以理解为：它忠实地执行了所有“必要”的松弛操作，最终达到的状态与Bellman-Ford相同。

核心思想：算法维护一个不变式：只要存在某个顶点 $v$ ，其最短路径估计值 $d[v]$ 还能被优化（即存在某条边 $(u,v)$ 使得 $d[v] > d[u] + w(u,v)$ ），那么 $u$ 最终一定会被加入队列，从而边 $(u,v)$ 会被松弛。

证明：我们再次使用反证法来证明，在没有负权环路的情况下，当SPFA算法终止时（队列为空），对所有可达顶点 $v$ ，都有 $d[v]=\delta(s,v)$ 。

算法终止性：在没有负权环路的图中，每个顶点的 $d$ 值是单调递减且有下界的（即真正的最短路 $\delta(s,v)$ ）。一个顶点的 $d$ 值更新次数是有限的（虽然可能很大）。因此，每个顶点入队的次数也是有限的。所以算法最终会终止。
结果正确性：
- 假设算法终止时，存在某个顶点 $v$ 使得 $d[v] > \delta(s,v)$ 。
- 在所有这类 $d$ 值不正确的顶点中，我们选择一个在从 $s$ 出发的某条真实最短路径上离 $s$ 最近的顶点，记为 $v$ 。（这里的“最近”指路径上的边数最少）。
- 设从 $s$ 到 $v$ 的一条最短路径为 $s \to v_1 \to v_2 \to \dots \to u \to v$ 。
- 由于 $v$ 是第一个不满足 $d[\cdot]=\delta(s,\cdot)$ 的顶点，那么它的前驱节点 $u$ 必然满足 $d[u] = \delta(s,u)$ 。
- 根据最短路径的性质，我们有： $\delta(s,v) = \delta(s,u) + w(u,v)$
- 将 $d[u] = \delta(s,u)$ 代入，得到： $\delta(s,v) = d[u] + w(u,v)$
- 结合我们最初的假设 $d[v] > \delta(s,v)$ ，可以推导出： $d[v] > d[u] + w(u,v)$
- 这个不等式是松弛边 $(u,v)$ 的条件。这意味着 $d[v]$ 还能被 $d[u]$ 更新。
- 现在我们来分析顶点 $u$ 的状态。在算法的某个时刻， $d[u]$ 一定是被更新为其最终值 $\delta(s,u)$ 的。每当一个顶点的 $d$ 值被更新，它就会被加入队列（如果不在队列中的话）。所以， $u$ 在其 $d$ 值被最后一次更新（更新为 $\delta(s,u)$ ）之后，一定入队了。
- 既然 $u$ 入队了，那么在未来的某个时间点，它必然会出队。当它出队时，算法会遍历所有从 $u$ 出发的边，其中就包括边 $(u,v)$ 。届时，算法会检查 $d[v] > d[u] + w(u,v)$ 是否成立。
- 根据我们上面的推导，这个条件是成立的。因此， $d[v]$ 必定会被更新（松弛）。
- 这次松弛会使得 $d[v] \le d[u] + w(u,v) = \delta(s,v)$ 。再结合上界性质 $d[v] \ge \delta(s,v)$ ，我们得到 $d[v]$ 在这次更新后会等于 $\delta(s,v)$ 。
- 这与我们的假设——“算法终止时 $d[v] > \delta(s,v)$ ”——相矛盾。
- 因此，假设不成立。当算法终止时，所有可达顶点的 $d[v]$ 都等于 $\delta(s,v)$ 。

证毕。

SPFA的负权环路检测

SPFA算法在有负权环路的情况下不会自行终止。因为环上顶点的 $d$ 值会无限减小，导致它们被反复加入队列。我们可以利用这个特性来检测负权环路。

一个简单而有效的方法是记录每个顶点入队的次数。

在一个不含负权环路的图中，一条从 $s$ 出发的最短路径是简单路径，其长度（边数）最多为 $|V|-1$ 。这意味着一个顶点的 $d$ 值最多被更新 $|V|-1$ 次（对应于路径长度从1到 $|V|-1$ 的情况）。
因此，如果某个顶点 $v$ 的入队次数达到了 $|V|$ 次，根据鸽巢原理，这说明从 $s$ 到 $v$ 的某条路径上至少有 $|V|$ 个顶点，这意味着该路径必然包含一个环。而每次更新都意味着找到了更短的路径，这只有在环是负权环时才可能发生。
所以，我们可以设置一个计数器 cnt[v]，记录每个顶点 $v$ 的入队次数。当一个顶点即将第 $|V|$ 次入队时，我们就可以断定图中存在负权环路。

代码实现

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100010;
ll d[N];
int h[N], e[N], ne[N], w[N], idx; // 邻接表存图
int cnt[N]; // 记录每个点入队次数
bool in_q[N]; // 标记是否在队列中

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa(int s, int n) {
    memset(d, 0x3f, sizeof d);
    d[s] = 0;

    queue<int> q;
    q.push(s);
    in_q[s] = true;
    cnt[s]++;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_q[u] = false;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (d[v] > d[u] + w[i]) {
                d[v] = d[u] + w[i];
                if (!in_q[v]) {
                    q.push(v);
                    in_q[v] = true;
                    cnt[v]++;
                    if (cnt[v] >= n) return true; // 发现负环
                }
            }
        }
    }
    return false; // 没有负环
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }

    if (spfa(1, n)) {
        cout << "Yes" << endl;
    } else {
        // 通常求最短路时会在这里输出d[n]等结果
        cout << "No" << endl;
    }

    return 0;
}

代码解释：
- 使用邻接表存储图，这对于稀疏图更高效。
- spfa 函数实现了算法核心逻辑。
- cnt 数组用于负权环检测。当 cnt[v] 达到 n 时，说明找到了负环，函数返回 true。
复杂度分析：
- 时间复杂度：
  - 最坏情况： $O(|V| \cdot |E|)$ 。SPFA的性能高度依赖于图的结构。在一些精心构造的图（例如网格图、链状图）上，SPFA的性能会退化，每个点可能被反复入队，总的松弛次数接近Bellman-Ford的水平。
  - 平均情况/随机图：通常被认为是 $O(k|E|)$ ，其中 $k$ 是一个小的常数。在大多数情况下，SPFA的效率远高于Bellman-Ford，接近于稀疏图上Dijkstra的效率。
- 空间复杂度： $O(|V| + |E|)$ 。用于邻接表、距离数组和队列。

Bellman-Ford与SPFA算法的正确性证明

预备知识与符号约定

Bellman-Ford算法及其正确性证明

算法描述

正确性证明

1. 最短路径计算的正确性

2. 负权环路检测的正确性

代码实现

SPFA算法及其正确性证明

算法描述

正确性证明

SPFA的负权环路检测

代码实现

评论

还没有账户？

登录