贝尔曼-福特算法是一种用于求解单源最短路径的算法，它的核心思想是通过多次松弛操作，逐步更新每个节点到源点的最短距离，直到所有距离不再发生变化或者检测到负权回路为止。该算法的时间复杂度为O(VE)，其中V是节点数量，E是边的数量，虽然效率不如迪杰斯特拉算法，但它可以处理带负权边的图，这是它的重要优势。
算法核心原理
贝尔曼-福特算法的执行流程可以分为两个主要阶段：
- 松弛阶段：对图中的每一条边进行V-1次松弛操作，每次松弛操作都会尝试用当前边的起点距离加上边权，来更新终点的最短距离。因为最短路径最多包含V-1条边，所以V-1次松弛足够覆盖所有可能的最短路径。
- 负权回路检测阶段：在完成V-1次松弛后，再对所有边进行一次遍历，如果还能继续更新距离，说明图中存在从源点可达的负权回路，此时最短路径不存在。
数据结构设计
我们首先定义边的结构体，存储每条边的起点、终点和权重：
struct Edge {
int u; // 起点
int v; // 终点
int w; // 边权
Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};
同时需要定义距离数组，存储每个节点到源点的最短距离，初始化时源点距离为0，其余节点距离为无穷大：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int INF = INT_MAX / 2; // 避免加法溢出
// 贝尔曼-福特算法实现函数
// 参数：节点数n，边集合edges，源点s
// 返回值：如果不存在负权回路返回true，否则返回false
bool bellmanFord(int n, const vector<Edge>& edges, int s, vector<int>& dist) {
// 初始化距离数组
dist.resize(n, INF);
dist[s] = 0;
// 执行V-1次松弛操作
for (int i = 0; i < n - 1; ++i) {
bool updated = false;
for (const auto& e : edges) {
if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
dist[e.v] = dist[e.u] + e.w;
updated = true;
}
}
// 如果本轮没有更新，提前结束
if (!updated) break;
}
// 检测负权回路
for (const auto& e : edges) {
if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
return false; // 存在负权回路
}
}
return true;
}
案例演示
我们构造一个包含负权边的图案例，节点编号为0到4，共5个节点，边的信息如下：
| 起点u | 终点v | 边权w |
|---|---|---|
| 0 | 1 | 4 |
| 0 | 2 | 5 |
| 1 | 3 | -2 |
| 2 | 1 | -3 |
| 2 | 3 | 3 |
| 3 | 4 | 2 |
| 1 | 4 | 1 |
我们以节点0为源点，调用bellmanFord函数计算最短路径，完整测试代码如下：
int main() {
int n = 5; // 5个节点
vector<Edge> edges;
// 添加边
edges.emplace_back(0, 1, 4);
edges.emplace_back(0, 2, 5);
edges.emplace_back(1, 3, -2);
edges.emplace_back(2, 1, -3);
edges.emplace_back(2, 3, 3);
edges.emplace_back(3, 4, 2);
edges.emplace_back(1, 4, 1);
int source = 0;
vector<int> dist;
if (bellmanFord(n, edges, source, dist)) {
cout << "从源点" << source << "到各节点的最短距离：" << endl;
for (int i = 0; i < n; ++i) {
if (dist[i] == INF) {
cout << "节点" << i << ": 不可达" << endl;
} else {
cout << "节点" << i << ": " << dist[i] << endl;
}
}
} else {
cout << "图中存在从源点可达的负权回路，最短路径不存在" << endl;
}
return 0;
}
运行结果分析
上述案例的运行结果如下：
从源点0到各节点的最短距离：
节点0: 0
节点1: 2
节点2: 5
节点3: 0
节点4: 2
结果说明：从节点0到节点1的最短路径是0->2->1，总权重为5 + (-3) = 2；到节点3的最短路径是0->2->1->3，总权重为5 + (-3) + (-2) = 0；到节点4的最短路径是0->2->1->4，总权重为5 + (-3) + 1 = 2，符合贝尔曼-福特算法的计算结果。
负权回路检测演示
如果我们修改边集合，添加一条从节点4到节点1的边，权重为-5，此时路径0->2->1->4->1->3会形成负权回路：
// 添加负权回路边 edges.emplace_back(4, 1, -5);
再次运行程序，算法会检测到负权回路，输出提示信息，说明此时最短路径不存在。
算法注意事项
- 距离数组初始化时，源点距离设为0，其余设为无穷大，无穷大的值不要设置得过大，避免加法溢出，可以使用INT_MAX/2作为无穷大的取值。
- 松弛阶段如果某一轮没有发生任何距离更新，可以提前终止循环，减少不必要的计算。
- 负权回路检测是在V-1次松弛之后进行，只有还能继续更新距离才说明存在负权回路，不能在第V-1次松弛过程中判断。
- 该算法只能检测到从源点可达的负权回路，如果负权回路从源点不可达，算法仍然会正常计算可达节点的最短路径。
Bellman_Ford负权边处理最短路径计算C++修改时间：2026-06-10 13:30:27