当前位置：首页 > news >正文

图论：SPFA算法

news 2025/8/2 14:28:48

Bellman_ford 队列优化算法，也叫SPFA算法，相对于贝尔曼-福德算法来说，SPFA用了队列进行优化，省去了一些多余的操作，本文会介绍一下基本的SPFA算法在例题中的应用以及对模板的整理，有需要的小伙伴可以保存起来。

SFPA（Algorithm for Shortest Path According to Flowing Priority）是一种单源最短路算法，它可以在边权有负值的情况下，找到从源节点到其他节点的最短路径。

大家可以发现 Bellman_ford 算法每次松弛都是对所有边进行松弛。

但真正有效的松弛，是基于已经计算过的节点在做的松弛。

只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。

SFPA算法的核心思想是根据节点的流动优先级来选择拓展的顺序，具体流程如下：

初始化：创建一个优先队列和一个标记数组，用来存储每个节点的最短距离和是否已经找到最短路径。

将源节点加入优先队列，并标记为已访问，设置源节点的最短距离为0。

重复以下步骤直到优先队列为空： a. 从优先队列中取出流动最大优先级的节点u。 b. 遍历节点u的所有邻居节点v，更新v的最短距离：

如果从u到v的路径长度加上边(u,v)的权值小于v的最短距离，则更新v的最短距离，并将v加入优先队列。 c. 标记节点u为已访问。
完成之后，最短路径的结果可以从标记数组中获得。

经典例题：

SPFA在算法竞赛中的应用

SPFA（Shortest Path Faster Algorithm）本质上是Bellman-Ford算法的队列优化版本，特别适合解决带负权边的单源最短路径问题。

何时选择SPFA？

必须使用SPFA的情况：
- 图中存在负权边（Dijkstra无法处理）
- 需要检测负权环（如差分约束系统）
推荐使用SPFA的情况：
- 稀疏图（边数E ≈ 顶点数V）
- 需要频繁更新最短路径（如动态图）
避免使用SPFA的情况：
- 稠密图（边数E接近V²）
- 确定没有负权边（直接用Dijkstra）
- 题目数据刻意卡SPFA（如网格图）

赛时易踩坑点：

常见坑点：
- 忘记初始化dis数组为INF
- 没有清空队列和inQueue数组（多组数据时）
- 把无向图当成有向图处理（少加反向边）

四大路径算法的对比：

算法	时间复杂度	可否处理负权边	可否检测负权环	适用场景
Dijkstra	O((V+E)logV)	否	否	无负权边的稀疏/稠密图
堆优化Dijkstra	O((V+E)logV)	否	否	无负权边的大规模图
Bellman-Ford	O(VE)	是	是	小规模图带负权边
SPFA	O(VE)~O(E)	是	是	稀疏图带负权边

路径问题三剑客：

学完最小生成树、堆优化版Dijkstra以及SPFA之后脑子更加迷糊了有没有，感觉都差不多但是又分不清哪个是哪个具体写的时候又不会，下面简单总结一下三者之间的关系。

一、核心使命

算法	核心任务	结果性质
最小生成树(Prim/Kruskal)	用最小成本连接所有点	形成一棵树（无环）
堆优化Dijkstra	找到单源点到其他点的最短路径	形成最短路径树
SPFA	带负权边的最短路径/检测负权环	可能包含负权环

形象理解：MST（最小生成树）是规划全城电网的最经济方案，Dijkstra是导航软件找最快路线，SPFA是考虑"倒贴钱"路线的导航

二、联系与区别速查

对比维度	最小生成树	堆优化Dijkstra	SPFA
数据结构	优先堆/并查集	优先堆	普通队列
边权要求	无方向性	必须非负	可正可负
时间复杂度	O(ElogV)	O(ElogV)	最差O(VE)平均O(E)
是否成环	绝对无环	可能隐含环	可能显式含负权环
典型应用	网络布线	导航最短路径	含负权的最短路问题

三、实战中的选择策略

当题目出现以下关键词时：

"连接所有节点"、"最小总成本" → 最小生成树
"最短路径"、"最少时间"、且无负权 → 堆优化Dijkstra
"可能盈利的路径"、"检测负权环" → SPFA

记住这三者的核心区别：MST关注全局连接成本，Dijkstra追求单源最短路径，SPFA解决含负权的特殊场景。

城市间货物运输I

题目链接：城市间货物运输

这道题用贝尔曼福德算法也是可以通过的，但是这里是用的SPFA来加深对这个算法的印象，首先就是需要用邻接表来存图，因为每一次都需要对这个点所连接的点进行遍历，而且还需要有一个数组用于标记当前的点是否在队列中，所以就从起点开始，每次将已经达到切不在队列中的点入队，然后在取出以上一次为基础再进行松弛操作，基于上述思路就有了一下代码：

#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;
vector<pii> e[N];
vector<int> ans(N,inf);
vector<bool> f(N,false);
queue<int> q;
int n,m;void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});}int start = 1,end = n;q.push(start);ans[start] = 0;while(!q.empty()){int index = q.front();q.pop();f[index] = false;for(auto &i : e[index]){int from = index;int to = i.fi;int value = i.se;if(ans[to] > ans[from] + value){ans[to] = ans[from] + value;if(!f[to]){f[to] = true;q.push(to);}}}}if(ans[end] == inf) cout<<"unconnected"<<endl;else cout<<ans[end]<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
}

依旧将模板整理如下：

图论的SPFA算法模板，XCPCer可拿~

#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;
vector<pii> e[N];    // 邻接表存图 e[u] = {v, w}
vector<int> ans(N,inf);  // 存储起点到各点的最短距离
vector<bool> f(N,false); // 标记顶点是否在队列中
queue<int> q;        // 用于优化的队列
int n,m;            // 顶点数，边数void solve()
{cin>>n>>m;// 初始化for(int i=0;i<=n;i++){e[i].clear();ans[i]=inf;f[i]=false;}while(!q.empty()) q.pop();// 建图for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});// 如果是无向图，添加反向边// e[v].push_back({u,w});}int start = 1, end = n; // 默认起点1，终点nans[start] = 0;q.push(start);f[start] = true;// SPFA主过程while(!q.empty()){int index = q.front();q.pop();f[index] = false;for(auto &i : e[index]){int to = i.fi;int value = i.se;// 松弛操作if(ans[to] > ans[index] + value){ans[to] = ans[index] + value;// 如果目标顶点不在队列中，加入队列if(!f[to]){q.push(to);f[to] = true;}}}}// 输出结果if(ans[end] == inf){cout<<"unconnected"<<endl; // 不可达}else{cout<<ans[end]<<endl;     // 输出最短距离}
}signed main()
{IOSint T=1;// cin>>T;  // 多组数据时取消注释while(T--){solve();}return 0;
}

【模板】负环

题目链接：【模板】负环

这道题是SPFA的板子题，对负环的判断有多种方式，可以统计这个点所连接的边数，也可以统计这个点入队的次数，如果超过了n-1就说明构成了负环，因为最短路最多有n-1条边。

方法 1

在 SPFA 算法的基础上，我们再添加一个统计每个结点入队次数的数组。
如果一个点入队超过了 n 次（即图上结点个数），则判断有负环。

方法 2

我们统计每两个点间的最短路包含多少条边，如果在一条最短路上包含超过了 (n−1) 条边，说明有边被重复使用，则判断有负环。

// Problem: P3385 【模板】负环
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3385
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#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 = 2e3 + 10;
vector<pii> e[N];
vector<bool> f(N,false);
vector<int> cnt(N,0),ans(N,inf);void init()
{fill(ans.begin(),ans.end(),inf);fill(f.begin(),f.end(),false);fill(cnt.begin(),cnt.end(),0);for(int i=0;i<N;i++) e[i].clear();
}
int n,m;void solve()
{queue<int> q;init();//别忘记初始化！cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});if(w>=0) e[v].push_back({u,w});}int start = 1;q.push(start);f[start] = true;ans[start] = 0;//千万别忘记！！！！！！！！！！！！！！！！！！！！！！！！while(!q.empty()){int index = q.front();q.pop();//这个也不能忘记！！！！！！f[index] = false;for(auto &i : e[index]){int to = i.fi;int value = i.se;if(ans[to] > ans[index] + value){ans[to] = ans[index] + value;if(!f[to]){f[to] = true;q.push(to);cnt[to]++;if(cnt[to] >= n){cout<<"YES"<<endl;return ;}}}}}cout<<"NO"<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
}

城市间货物运输II

题目链接：城市间货物运输II

这道题和上面的类似，就是增加了一个对负环的判断，不再过多解释，代码如下：

#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;
vector<int> ans(N,inf);//别忘记初始化
vector<pii> e[N];
vector<bool> inq(N,false);
vector<int> cnt(N,0);
queue<int> q;
int n,m;void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});}int start = 1,end = n;ans[start] = 0;q.push(start);inq[start] = true;while(!q.empty()){int index = q.front();q.pop();inq[index] = false;for(auto &i : e[index]){int to = i.fi;int value = i.se;if(ans[to] > ans[index] + value){ans[to] = ans[index] + value;if(!inq[to]){q.push(to);inq[to] = true;cnt[to]++;if(cnt[to] >= n){cout<<"circle"<<endl;return ;}}}}}if(ans[end] == inf) cout<<"unconnected"<<endl;else cout<<ans[end]<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
}

队列优化版Bellman_ford 的时间复杂度并不稳定，效率高低依赖于图的结构。

查看全文

http://www.lryc.cn/news/606356.html