贝尔曼-福特算法核心是通过n-1轮松弛操作，用所有边逐轮更新最短距离，可处理负权边但无法处理负权环；C++实现需用LLONG_MAX/2初始化、检测更新提前终止，并通过第n轮判断可达负权环。
贝尔曼-福特算法的核心逻辑是什么
贝尔曼-福特算法本质是通过 n-1 轮松弛操作，逐步逼近每个节点到源点的最短距离；它能处理含负权边的图，但不能处理存在负权环的图（否则最短路径无定义）。关键不在于“多轮迭代”，而在于每轮都尝试用所有边更新距离——这保证了即使最远路径需要经过 n-1 条边，也能在第 n-1 轮被收敛。
如何用 C++ 实现标准版 Bellman-Ford
使用 vector<tuple<int, int, int>> 存储边（起点、终点、权重），配合 vector<long long> 维护距离数组。注意初始化为 LLONG_MAX / 2（避免后续加法溢出），源点设为 0。
#include <vector>
#include <tuple>
#include <climits>
#include <iostream>
using namespace std;
<p>vector<long long> bellman_ford(int n, vector<tuple<int, int, int>>& edges, int src) {
vector<long long> dist(n, LLONG_MAX / 2);
dist[src] = 0;</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < n - 1; ++i) {
bool updated = false;
for (auto& [u, v, w] : edges) {
if (dist[u] != LLONG_MAX / 2 && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
if (!updated) break; // 提前终止
}
return dist;}
-
n是顶点数（编号从0到n-1） - 边列表可含重复或反向边，不影响正确性
- 提前终止条件（
updated == false）对稀疏图很有效，但不能跳过第n-1轮检测负环
怎么检测图中是否存在负权环
运行完 n-1 轮松弛后，再执行一轮：若任意边仍能更新距离，则说明存在从源点可达的负权环。注意——只检测“从源点出发能到达的负环”，孤立负环不会触发。
立即学习“C++免费学习笔记（深入）”；
bool has_negative_cycle(int n, vector<tuple<int, int, int>>& edges, int src) {
vector<long long> dist(n, LLONG_MAX / 2);
dist[src] = 0;
<pre class='brush:php;toolbar:false;'>for (int i = 0; i < n - 1; ++i) {
for (auto& [u, v, w] : edges) {
if (dist[u] != LLONG_MAX / 2 && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// 第 n 轮检测
for (auto& [u, v, w] : edges) {
if (dist[u] != LLONG_MAX / 2 && dist[u] + w < dist[v]) {
return true;
}
}
return false;}
- 必须用同一套
dist数组连续跑n轮，不能重置 - 若只需判断负环存在性，无需保存中间距离，可省去提前终止
- 若图不连通，且负环不在源点连通分量内，该函数返回
false——这是预期行为，不是 bug
实际使用时最容易踩的坑
负权边本身不危险，危险的是没意识到 Bellman-Ford 的“可达性前提”和整数溢出风险。
- 输入边时忘记检查
u和v是否在[0, n)范围内，导致越界访问 - 用
INT_MAX初始化dist，遇到负权边做加法时直接溢出成负数，后续比较全乱 - 误以为返回
LLONG_MAX / 2就代表“不可达”，其实应判断是否仍等于初始值（因为负权路径可能真达到极大正值） - 多源点场景下直接复用单源实现，结果只算出一个源点的结果——Bellman-Ford 本就是单源算法，多源需多次调用或改用 Floyd
负权边能算，但得确保你真正需要它；多数业务场景里，出现负权往往意味着建模错误，先确认是不是权重含义理解反了，比急着写松弛更关键。
