图论——Bellman-Ford和SPFA

Bellman-Ford & SPFA

这两者实现的操作是一样的，前者比较能反应该算法的原理，较为直观。而后者则是它的优化版本。

先贴一道模板题：P3385 【模板】负环 - 洛谷

Bellman-Ford

算法介绍

Bellman-Ford算法的应用场景是什么呢？在前面的Djikstra算法中，我们用它处理单源点到图中所有点的最小距离，前提是所有边权皆为正。但是当一些问题中边权为负的时候就会出错。下面用一张图表简单看一下：

核心维度	Dijkstra 算法	Bellman-Ford 算法
边权限制	仅支持非负权边（有负权边时结果错误）	支持负权边（无限制）
负环处理	无法检测负环，甚至可能因负权边输出错误结果	能检测从起点可达的负环（N-1 轮后仍可松弛）
时间效率	高（优化版 O (M log N)）	低（朴素版 O (N*M)）
核心思想	贪心：每次确定 “当前最短顶点” 的路径，不再更新	动态规划：通过 N-1 轮松弛所有边，逐步逼近最短路径

接下来详细解释一下两者的功能区别：

          [1]  （起点，方框代表顶点）/   \3 /     \  5/       \[2] ←─────── [3]  （终点）-3

假设有这么一张图，现在我要求1->2的最短距离。用Djikstra算法的思想：很明显，因为边权5>3，所以会选择直接从1->2而不会选择先到3再到2。因为此算法是局部的贪心，并不会考虑到负边权的情况。可以看到，事实是如果再从3->2的话边权会更小。

其实Bellman-Ford就是将所有能遍历的点都给遍历一遍，做一个“全局贪心”。那么代价就是由于它并不会提前结束遍历，时间复杂度会高于Djikstra.所以在解决没有负边权的时候优先使用Djikstra算法。

代码解释

void bellmanFord(int n) 
{vector<int> dis(n+1, INF);dis[1] = 0;for(int i=1; i<n; ++i) // 进行n-1次松弛操作 {bool updated = false;for (int j = 0; j < edge.size(); ++j) {int u = edge[j].u;int v = edge[j].v;int w = edge[j].w;// 如果可以松弛，就更新距离if (dis[u] != INF && dis[v] > dis[u] + w) {dis[v] = dis[u] + w;updated = true;}}if(!updated) break;  // 没有更新，提前结束}// 检测负环：如果还能松弛，说明存在负环for(int j = 0; j < edge.size(); ++j){int u = edge[j].u;int v = edge[j].v;int w = edge[j].w;if(dis[u] != INF && dis[v] > dis[u] + w) // 存在负环{cout << "存在负环" << endl;return ;}}for(int i=1; i<=n; i++) cout << dis[i] <<' ';//输出起点到图上其他点的最短距离cout << endl;
}
void solve() 
{int n, m;cin >> n >> m;for(int i = 0; i < m; ++i) {int u,v,w;cin >> u >> v >> w;edge.push_back({u,v,w});}bellmanFord(n);
}

---

SPFA（Shortest Path Fastest Algorithm）

通过名字就可以感受到这个算法又短又快，其实它是Bellman-Ford的优化版本，其大致原理是一致的。

• 队列优化：本算法仅将可能松弛的点放到队列里面，避免对每个点都进行遍历的冗余操作。
• 负环检测：记录每个顶点的入队次数，若某个顶点入队次数超过 n（顶点总数），则说明存在从起点可达的负环（因为正常最短路径最多经过 n 个顶点，入队次数不会超过 n）。

代码解释

int dis[N],cnt[N];
struct node  {int v; int w;
};
vector<node> g[N];
queue<int> q;
int x,y,z;
bool SPFA(int x)
{dis[x] = 0;q.push(x);while(q.size()){int u = q.front();q.pop();for(auto i:g[u]){int nv = i.v;int nw = i.w;if(dis[nv] > dis[u] + nw){dis[nv] = dis[u] + nw;if(++cnt[nv] >= n) return 1; //是负环q.push(nv);}}}return 0;
}
void solve()
{memset(dis,0x3f,sizeof(dis));memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;i++) g[i].clear(); //初始化邻接表cin >> n >> m;for(int i=1;i<=m;i++){cin >> x >> y >> z;g[x].push_back({y,z});if(z >= 0) g[y].push_back({x,z});//存图 只有正数才存双向边}if(SPFA(1)) cout << "YES" << endl;else cout << "NO" << endl;
}