图论：Bellman_ford算法
在求解单源最短路的时候，前面的文章中介绍的一种Dijkstra算法，但是Dijkstra算法只适用于边权没有负数的情况，当图中存在负边权时，后续发现的负权路径可能会让 “已确定” 的节点距离变得更短，但 Dijkstra 算法无法处理这种情况。
回顾Dijkstra
Dijkstra 算法的工作流程可以概括为：
- 初始化：起点到自身的距离为 0，到其他所有节点的距离为 “无穷大”。
- 贪心选择：每次从 “未确定最短路径的节点” 中，选择当前距离起点最近的节点（记为
u），并标记u的最短路径已 “确定”（此后不再修改）。- 松弛操作：以
u为中介，更新所有与u相邻的节点（记为v）的距离：若起点→u→v的距离比当前起点→v的距离更短，则更新v的距离。- 重复步骤 2-3：直到所有节点的最短路径都被确定。
其核心假设是：一旦某个节点被标记为 “最短路径已确定”，就无需再考虑它的距离更新 —— 因为非负边权不会让后续路径比当前更短。
二者的区别
| 特性 | Dijkstra 算法 | Bellman-Ford 算法 |
|---|---|---|
| 适用边权 | 仅支持非负边权（无负权边） | 支持负边权，但不支持含负权回路的图（否则最短路径无意义） |
| 时间复杂度 | 优化后（堆 + 邻接表）为 \(O((n+m)\log n)\)（高效） | 朴素版为 \(O(n \times m)\)（低效） |
| 核心逻辑 | 贪心策略（每次选当前最短距离节点，确定后不再更新） | 松弛策略（对所有边重复松弛 n-1 次，允许反复更新） |
| 优势场景 | 非负边权图（如道路导航、多数实际工程场景） | 含负边权但无负权回路的图（如金融交易中的 “负成本” 场景） |
- Dijkstra：仅能处理非负边权，但效率极高，是非负边权图的 “最优解”；
- Bellman-Ford：能处理负边权（无负回路），但效率低，是负边权场景的 “必要解”。
总之：
- 当图中存在负边权（且无负回路）：只能用 Bellman-Ford（或其优化版 SPFA），此时 Dijkstra 无法使用；
- 当图中只有非负边权：必须用 Dijkstra（或更高效的 A * 等衍生算法），此时 Bellman-Ford 效率过低，完全不适用。
Bellman-Ford算法
Bellman-Ford 算法是求解单源最短路径问题的经典算法，与 Dijkstra 算法相比，它的优势在于支持负边权，但时间复杂度较高。
Bellman-Ford 算法的核心思想是动态规划，通过对所有边进行松弛操作来逐步逼近最短路径。具体流程如下：
- 初始化：将起点到自身的距离设为 0，到其他节点的距离设为无穷大（通常用一个足够大的数表示）。
- 松弛操作：对图中的每条边
(u, v, w)（表示从节点u到节点v的边权为w），如果dist[u] + w < dist[v]，则更新dist[v] = dist[u] + w。- 重复松弛：重复步骤 2 的松弛操作，最多进行
n-1轮（n为节点数）。这是因为任意两个节点间的最短路径最多经过n-1条边。- 检查负环：在完成
n-1轮松弛后，再进行一轮松弛操作。如果此时仍存在边可以被松弛，则说明图中存在负权回路（总权值为负的环），导致最短路径无限小，问题无解。
在算法竞赛中的应用
Bellman-Ford 算法在算法竞赛中主要用于以下场景：
1. 处理负边权问题
当题目中的边权可能为负数时，Dijkstra 算法失效，必须使用 Bellman-Ford。例如：
- 最短路变形题：某些边权为负，但保证无负环。
- 差分约束系统：将不等式转化为图的边，用 Bellman-Ford 求解可行解。
2. 检测负权回路
算法的第 4 步可用于判断图中是否存在负环，这是竞赛中的常见考点。例如：
- 题目描述：判断一个图是否存在总权值为负的环。
- 解法：运行 Bellman-Ford，若第
n轮仍能松弛，则存在负环。
优化版的SPFA算法会在几天后更新。
城市间货物运输I
题目链接：城市间货物运输I
本题是经典的带负权值的单源最短路问题，此时就轮到Bellman_ford登场了，接下来我们来介绍一下Bellman_ford 算法如何解决这类问题。Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离，这里说的是一条边相连的节点。
详解代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e3+10;
void solve()
{int n,m;cin>>n>>m;vector<vector<int>> e;vector<int> ans(n+1,inf);//用于存最短距离（最小代价） 且初始化为最大for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e.push_back({u,v,w});//无需建图 直接将每一组存起来即可}int start = 1,end = n;ans[start] = 0;//对起点初始化for(int i=1;i<n;i++){//松弛n-1次 每一次都遍历所有的边权 每一次都代表着一条路for(auto &i : e)//加 “&” 节省时间！{if(ans[i[0]] == inf) continue;//i[0]为上一次的终点 i[1]为这一次的终点 i[2]为这两点之间的权值！if(ans[i[1]] > ans[i[0]] + i[2]) ans[i[1]] = ans[i[0]] + i[2];//松弛操作}}// cout<<(ans[n] == inf ? "unconnected" : ans[n]);if(ans[n] == inf) cout<<"unconnected"<<endl;else cout<<ans[n]<<endl;
// cout<<fixed<<setprecision(x)<< ;
}signed main()// Don't forget pre_handle!
{IOSint T=1;
// cin>>T;while(T--) solve(); return 0;
}
Bellman_ford算法模板
这里整理的模板，有需要的ICPCer可拿！
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pii pair<int, int>
#define fi first
#define se second
// 常量定义：根据题目最大数据范围调整
const int inf = 0x3f3f3f3f3f3f3f3f; // 表示“无穷大”（long long类型，避免溢出）
const int MAXN = 1e5 + 10; // 最大节点数（根据题目调整，如1e5、1e4）
const int MAXM = 2e5 + 10; // 最大边数（通常为节点数的2倍，适应无向图）
// 全局变量：避免函数参数传递，简化调用
int n, m; // n：节点总数；m：边总数
vector<vector<int>> e; // 存储所有边（每个元素为{u, v, w}，表示u到v的边权为w）
vector<int> ans; // 存储“起点到各节点的最短距离”（下标对应节点编号）
bool hasNegativeCycle; // 标记图中是否存在负环（从起点可达的负环）
// Bellman-Ford核心算法：求解单源最短路径 + 检测负环
// 参数：start -> 起点编号
void bellman_ford(int start)
{// 1. 初始化距离数组ans.assign(n + 1, inf); // 所有节点初始距离为“无穷大”ans[start] = 0; // 起点到自身的距离为0// 2. 松弛操作：最多执行n-1次（最短路径最多含n-1条边）for (int i = 1; i < n; i++) // i表示“当前松弛的路径最多含i条边”{bool updated = false; // 优化标记：本轮是否更新过距离// 遍历所有边，尝试松弛for (auto &edge : e) // 用引用&遍历，避免拷贝边的临时对象（加速）{int u = edge[0]; // 边的起点int v = edge[1]; // 边的终点int w = edge[2]; // 边的权值// 若起点u不可达（距离为inf），则无需松弛vif (ans[u] == inf)continue;// 松弛操作：若“起点->u->v”比当前“起点->v”更近，则更新v的距离if (ans[v] > ans[u] + w){ans[v] = ans[u] + w;updated = true; // 标记本轮有更新}}// 若本轮无任何更新，说明所有最短路径已确定，提前退出（减少无效循环）if (!updated) break;}// 3. 检测负环：执行第n次松弛，若仍能更新则存在负环hasNegativeCycle = false; // 先默认无负环for (auto &edge : e){int u = edge[0];int v = edge[1];int w = edge[2];if (ans[u] == inf) continue;// 若还能松弛，说明存在从起点可达的负环（可无限缩短路径）if (ans[v] > ans[u] + w){hasNegativeCycle = true;break; // 找到负环后直接退出检测}}
}
// 主逻辑处理函数：读取输入 + 调用算法 + 输出结果
void solve()
{// 读取节点数和边数cin >> n >> m;// 清空上一轮的边（避免多测试用例时数据残留）e.clear();// 读取m条边，存入全局变量efor (int i = 0; i < m; i++){int u, v, w;cin >> u >> v >> w;e.push_back({u, v, w}); // 存储边：u->v，权值w}// 设定起点（题目通常为1，可根据实际修改）int start = 1;// 调用Bellman-Ford算法计算最短路径bellman_ford(start);// 先判断是否存在负环（若有，最短路径无意义）if (hasNegativeCycle){cout << "存在负环，最短路径无效" << endl;return;}// 设定终点（题目通常为n，可根据实际修改）int end = n;// 输出结果：判断终点是否可达if (ans[end] == inf) cout << "unconnected" << endl; // 终点不可达else cout << ans[end] << endl; // 输出最短距离
}// 程序入口
signed main()
{IOSint T = 1;// cin >> T;while (T--) solve();return 0;
}愿大家的付出都有回报，我也是。