一、算法应用场景

$Bellman-Ford$算法是解决单源最短路径问题的经典算法，特别适合以下场景：

1. 带负权边的图（$Dijkstra$算法无法处理）
2. 需要检测负权环的存在
3. 限制路径边数的最短路径

二、算法核心思想

通过反复对图中的所有边进行松弛操作（$Relaxation$），逐步逼近最短路径。算法保证在经过$n-1$轮松弛后（$n$为节点数），如果没有负权环，就能得到最终解。

三、算法步骤详解

1. 初始化：设置起点距离为$0$，其他节点距离为无穷大
2. 松弛操作：对每条边进行遍历，尝试用当前边缩短目标节点的距离
3. 迭代次数：
   • 最多进行$n-1$次迭代（$n$为节点数）
   • 如果题目限制边数$k$，则进行$k$次迭代

假设我们有一个图，节点为 A, B, C, D，起点为 A，边的信息如下：

边	起点	终点	权重
1	A	B	2
2	A	C	4
3	B	C	1
4	B	D	7
5	C	D	3

初始状态

节点	距离（初始）
A	0
B	∞
C	∞
D	∞

---

松弛过程

第 1 轮松弛

边	操作	更新后距离
1	dist[B] = min(∞, 0 + 2)	2
2	dist[C] = min(∞, 0 + 4)	4
3	dist[C] = min(4, 2 + 1)	3
4	dist[D] = min(∞, 2 + 7)	9
5	dist[D] = min(9, 3 + 3)	6

第 1 轮松弛后距离表

节点	距离
A	0
B	2
C	3
D	6

---

第 2 轮松弛

边	操作	更新后距离
1	dist[B] = min(2, 0 + 2)	2
2	dist[C] = min(3, 0 + 4)	3
3	dist[C] = min(3, 2 + 1)	3
4	dist[D] = min(6, 2 + 7)	6
5	dist[D] = min(6, 3 + 3)	6

第 2 轮松弛后距离表

节点	距离
A	0
B	2
C	3
D	6

---

第 3 轮松弛

边	操作	更新后距离
1	dist[B] = min(2, 0 + 2)	2
2	dist[C] = min(3, 0 + 4)	3
3	dist[C] = min(3, 2 + 1)	3
4	dist[D] = min(6, 2 + 7)	6
5	dist[D] = min(6, 3 + 3)	6

第 3 轮松弛后距离表

节点	距离
A	0
B	2
C	3
D	6

---

结果分析

• 在第 2 轮松弛后，距离表已经不再更新，说明算法提前收敛。
• 最终的最短路径距离为：
  • A → B：2
  • A → C：3
  • A → D：6

四、时间复杂度分析

• 时间复杂度：$O(k\ast m)$（$k$为迭代次数，$m$为边数）
• 空间复杂度：$O(m)$（存储边信息）

五、关键代码解析

void bellman_ford(int start, int end, int k) {
    // 初始化距离数组
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;

    for(int i=1; i<=k; i++) {
        memcpy(backup, dist, sizeof backup); // 备份防止串联更新
        for(int j=1; j<=edge_num; j++) {
            int from = from_nodes[j];
            int to = to_nodes[j];
            int weight = weights[j];
            // 松弛操作核心代码
            dist[to] = min(dist[to], backup[from] + weight);
        }
    }
}

---

为什么需要备份数组？

1. 防止串联更新：

   • 备份数组确保每一轮松弛操作都基于上一轮的结果，而不是当前轮次的部分结果。
   • 这样可以保证每一轮松弛只扩展一条边，符合 Bellman-Ford 算法的正确性要求。

2. 保证算法正确性：

   • Bellman-Ford 算法的正确性依赖于每一轮松弛只更新最多经过 k 条边的最短路径。
   • 如果不使用备份数组，可能会导致单轮松弛中多次使用同一条边，从而破坏算法的正确性。

---

例子说明

假设我们有一个图，节点为 A, B, C，起点为 A，边的信息如下：

边	起点	终点	权重
1	A	B	1
2	B	C	1
3	A	C	3

我们希望计算从 A 到其他节点的最短路径。

---

不使用备份数组的情况

初始状态

节点	距离（初始）
A	0
B	∞
C	∞

---

第 1 轮松弛

1. 处理边 A → B：

   • dist[B] = min(∞, dist[A] + 1) = min(∞, 0 + 1) = 1
   • 更新后 dist[B] = 1

2. 处理边 B → C：

   • dist[C] = min(∞, dist[B] + 1) = min(∞, 1 + 1) = 2
   • 更新后 dist[C] = 2

3. 处理边 A → C：

   • dist[C] = min(2, dist[A] + 3) = min(2, 0 + 3) = 2
   • 无需更新

第 1 轮松弛后距离表

节点	距离
A	0
B	1
C	2

---

问题分析

• 在第 1 轮松弛中，我们通过边 A → B 更新了 dist[B]，然后立即用更新后的 dist[B] 更新了 dist[C]。
• 这种立即使用当前轮次更新结果的行为就是串联更新。
• 串联更新会导致算法在单轮松弛中多次使用同一条边，从而破坏 Bellman-Ford 算法的正确性。因为第一轮的dist数组状态定义为最多经过1条边的最短路，而A → C实际是经过了A → B → C，并不符合要求。

---

使用备份数组的情况

初始状态

节点	距离（初始）
A	0
B	∞
C	∞

---

第 1 轮松弛

1. 备份当前距离数组：

   • backup = {0, ∞, ∞}

2. 处理边 A → B：

   • dist[B] = min(∞, backup[A] + 1) = min(∞, 0 + 1) = 1
   • 更新后 dist[B] = 1

3. 处理边 B → C：

   • dist[C] = min(∞, backup[B] + 1) = min(∞, ∞ + 1) = ∞
   • 无需更新

4. 处理边 A → C：

   • dist[C] = min(∞, backup[A] + 3) = min(∞, 0 + 3) = 3
   • 更新后 dist[C] = 3

第 1 轮松弛后距离表

节点	距离
A	0
B	1
C	3

---

第 2 轮松弛

1. 备份当前距离数组：

   • backup = {0, 1, 3}

2. 处理边 A → B：

   • dist[B] = min(1, backup[A] + 1) = min(1, 0 + 1) = 1
   • 无需更新

3. 处理边 B → C：

   • dist[C] = min(3, backup[B] + 1) = min(3, 1 + 1) = 2
   • 更新后 dist[C] = 2

4. 处理边 A → C：

   • dist[C] = min(2, backup[A] + 3) = min(2, 0 + 3) = 2
   • 无需更新

第 2 轮松弛后距离表

节点	距离
A	0
B	1
C	2

---

结果对比

• 不使用备份数组：
  • 第 1 轮松弛后，dist[C] = 2（错误，因为单轮松弛中使用了多条边）
• 使用备份数组：
  • 第 1 轮松弛后，dist[C] = 3
  • 第 2 轮松弛后，dist[C] = 2（正确）

---

总结

• 备份数组的作用是确保每一轮松弛操作基于上一轮的完整结果，而不是当前轮次的部分结果。
• 通过备份数组，我们可以避免串联更新，从而保证 Bellman-Ford 算法的正确性。

六、算法正确性证明（数学归纳法）

命题：经过$k$次迭代后，$dist$数组中存储的是最多经过$k$条边的最短路径

证明：

1. 基例（$k=0$）：

   • 只有起点距离为$0$，符合$0$条边的路径

2. 归纳假设：

   • 假设$k$次迭代后，$dist[v]$存储的是最多经过$k$条边到达$v$的最短距离

3. 归纳步骤：

   • 在第$k+1$次迭代中，对于边$(u,v,w)$
   • 若存在路径$s->...->u->v$，且$s$到$u$的最短路径经过$k$条边
   • 则通过松弛操作可以更新$v$的最短距离为$min(dist[v],dist[u]+w)$
   • 这正好对应最多经过$k+1$条边的情况

结论：经过$k$次迭代后，算法正确计算最多经过$k$条边的最短路径

七、处理负权环

Bellman-Ford 算法的一个重要功能是检测图中是否存在负权环。负权环是指图中存在一个环，其边的权重之和为负数。这样的环会导致路径无限缩短（绕环次数越多，总权值越小），从而使得最短路径问题无解。

---

1. 负权环检测方法

在 Bellman-Ford 算法中，负权环的检测方法如下：

1. 进行 $n-1$ 轮松弛操作（$n$ 为节点数），得到每个节点的最短路径。
2. 再进行第 $n$ 轮松弛操作：
   • 如果第 $n$ 轮松弛操作中仍有节点的距离被更新，说明图中存在负权环。
   • 如果没有更新，则说明图中不存在负权环。

---

2. 负权环检测的正确性证明

鸽巢原理回顾

鸽巢原理（Pigeonhole Principle）指出，如果将 $m$ 个物体放入 $n$ 个鸽巢中，且 $m>n$，则至少有一个鸽巢中会有超过一个物体。

应用到 Bellman-Ford 算法

1. 最短路径的性质：

   • 在一个没有负权环的图中，最短路径最多包含 $n-1$ 条边（$n$ 为节点数）。
   • 这是因为如果路径包含 $n$ 条边，则路径中至少有一个节点被重复访问，形成了环。如果环的权重非负，则去掉这个环可以得到更短的路径；如果环的权重为负，则路径可以无限缩短。

2. 第 $n$ 轮松弛的意义：

   • 如果第 $n$ 轮松弛操作中仍有节点的距离被更新，说明存在一条路径，其边数至少为 $n$。
   • 根据鸽巢原理，这条路径中至少有一个节点被重复访问，形成了一个环。
   • 如果这个环的权重为负，则在第$n$轮中可以继续更新最短路

3. 详细推导：

   • 假设图中存在一个负权环 $C$，其权重为 $w(C)<0$。
   • 对于环上的任意节点 $v$，我们可以通过绕环多次来不断缩短 $v$ 的距离：
     • 第一次绕环：距离减少 $w(C)$
     • 第二次绕环：距离再减少 $w(C)$
     • 依此类推，距离可以无限缩短。
   • 在第 $n$ 轮松弛操作中，算法会尝试用包含 $n$ 条边的路径更新距离。
   • 如果路径中包含负权环，则距离会被更新，说明存在负权环。

---

4. 总结

• Bellman-Ford 算法通过第 $n$ 轮松弛操作检测负权环。
• 鸽巢原理保证了如果第 $n$ 轮松弛操作中仍有节点的距离被更新，则图中存在负权环。
• 这种检测方法的时间复杂度为 $O(n\cdot m)$（$n$ 为节点数，$m$ 为边数），与 Bellman-Ford 算法本身的时间复杂度一致。

八、算法优化技巧

1. 提前终止：如果某轮迭代没有发生任何更新，可以提前结束
2. 队列优化：$SPFA$算法（队列优化的$Bellman-Ford$）

九、与Dijkstra算法对比

特性	Bellman-Ford	Dijkstra
负权边处理	✅	❌
时间复杂度	O(k*m)	O(m logn)
空间复杂度	O(m)	O(n)
适用场景	带负权边/限制边数	正权图

十、实际应用案例

1. 网络路由协议中的路径选择
2. 金融系统中的套利检测（负权环检测）
3. 交通规划中的限时送达路径计算

练习建议：ACWing 边数限制的最短路
尝试修改代码实现以下功能：

• 检测图中是否存在负权环
• 输出具体的最短路径（而不仅仅是距离）
• 实现队列优化版本（$SPFA$）

Sample Code

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1e4+7;   // 最大节点数
int node_num, edge_num, k_limit;  // 节点数、边数、允许的最大边数
int from_nodes[MAXN], weights[MAXN], to_nodes[MAXN], edge_count; // 边的起点、权重、终点数组
int dist[MAXN], backup[MAXN];      // 距离数组和备份数组

void add_edge(int from, int to, int weight) {
    from_nodes[++edge_count] = from;
    weights[edge_count] = weight;
    to_nodes[edge_count] = to;
}

void bellman_ford(int start, int end, int k) {
    memset(dist, 0x3f, sizeof dist);  // 初始化为无穷大
    dist[start] =  0;  // 起点距离设为0

    for(int i=1; i<=k; i++) {  // 进行k次松弛操作
        memcpy(backup, dist, sizeof backup);  // 备份防止串联更新
        for(int j=1; j<=edge_num; j++) {  // 遍历所有边
            int from = from_nodes[j];
            int to = to_nodes[j];
            int weight = weights[j];
            // 松弛操作：尝试用这条边缩短距离
            dist[to] = min(dist[to], backup[from] + weight);
        }
    }

    if(dist[end] >= 0x3f3f3f3f / 2) 
        cout << "impossible";  // 不可达的情况
    else 
        cout << dist[end];     // 输出最短距离
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> node_num >> edge_num >> k_limit;
    for(int i=1; i<=edge_num; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add_edge(x, y, z);
    }
    bellman_ford(1, node_num, k_limit);
    return 0;
}