浅谈 SPFA
原创
前言：
大家好，我是 Clare613，今天和大家好好唠一唠 SPFA。
SPFA 算法简介：
何为 SPFA：
SPFA 算法是 Bellman-Ford 算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。
有什么用：
SPFA 作为最基础的单源最短路，个人认为类似于 BFS，代码大概是这样的：
void SPFA(){
memset(cnt,0x3f,sizeof(cnt));
queue<int> q;
q.push(s);
cnt[s]=0;
f[s]=1;
while(!q.empty()){
int t=q.front();
q.pop();
f[t]=0;
for(auto i:a[t]){
if(cnt[i.v]>cnt[t]+i.w){
cnt[i.v]=cnt[t]+i.w;
if(!f[i.v]){
q.push(i.v);
f[i.v]=1;
}
}
}
}
}貌似对于新手不太友好，这里我们需要明确松弛操作。松弛操作是至当有一个点走到另一个点时，如果速度比原来速度快，那么就执行赋值操作，这就叫做松弛操作。除了松弛操作，就只剩下入队的问题，其实很简单，如果你在队里就不加，否则就加。
举个例子：
我们从 1 开始，dis 数组表示每一个点到一的当前最短距离，即之后会有所改变。队列 q 用于存储松弛操作的点。
无向图：
【第零步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | INF | INF | INF | INF | INF | INF |
q:1。
解释：最开始只有一个数 1,表示起点。
【第一步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | INF | INF | 5 | INF |
q:2,3,6。
解释：q 中取出 1，将 2,3,6 的值进行松弛操作，然后将其加入队列。
【第二步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | INF | 5 | 5 |
q:3,6,4,7。
解释：q 中取出 2，可以发现 2 的 dis_2+2 大于 dis_1，于是不能对 1 进行松弛操作。将 4,7 的值进行松弛操作，然后将其加入队列。
【第三步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:6,4,7,5。
解释：q 中取出 3，可以发现 3 的 dis_3+1 大于 dis_1，于是不能对 1 进行松弛操作。可以发现 3 的 dis_3+3 等于 dis_4，于是不必对 4 进行松弛操作。将 5 的值进行松弛操作，然后将其加入队列。
【第四步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:4,7,5。
解释：q 中取出 6，可以发现没有数可以进行松弛操作，直接淘汰。
【第五步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:7,5。
解释：q 中取出 4，可以发现没有数可以进行松弛操作，直接淘汰。
【第六步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:5。
解释：q 中取出 7，可以发现没有数可以进行松弛操作，直接淘汰。
【第七步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 4 | 5 |
q:6。
解释：q 中取出 5，可以发现 6 可以进行松弛操作。将 6 的值进行松弛操作，然后将其加入队列。
【第八步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 4 | 5 |
q:无。
解释：q 中取出 6，可以发现没有数可以进行松弛操作，直接淘汰。
有向图：
【第零步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | INF | INF | INF | INF | INF | INF |
q:1。
解释：最开始只有一个数 1,表示起点。
【第一步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | INF | INF | 5 | INF |
q:2,3,6。
解释：q 中取出 1，将 2,3,6 的值进行松弛操作，然后将其加入队列。
【第二步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | INF | 5 | 5 |
q:3,6,4,7。
解释：q 中取出 2。将 4,7 的值进行松弛操作，然后将其加入队列。
【第三步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:6,4,7,5。
解释：q 中取出 3，可以发现 3 的 dis_3+3 等于 dis_4，于是不必对 4 进行松弛操作。将 5 的值进行松弛操作，然后将其加入队列。
【第四步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:4,7,5。
解释：q 中取出 6，可以发现没有数可以进行松弛操作，直接淘汰。
【第五步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:7,5。
解释：q 中取出 4，可以发现没有数可以进行松弛操作，直接淘汰。
【第六步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 5 | 5 |
q:5。
解释：q 中取出 7，可以发现没有数可以进行松弛操作，直接淘汰。
【第七步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 4 | 5 |
q:6。
解释：q 中取出 5，可以发现 6 可以进行松弛操作。将 6 的值进行松弛操作，然后将其加入队列。
【第八步】：
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
dis_i | 0 | 2 | 1 | 4 | 3 | 4 | 5 |
q:无。
解释：q 中取出 6，可以发现没有数可以进行松弛操作，直接淘汰。
例题演练：
本期的题目均在洛谷中可以查到，分配如下：
P3371，P3385 现在讲。
P1821，P3115，P3063，P5837 为练习题。
P3371 【模板】单源最短路径（弱化版）：
这是 SPFA 的基础题，按照前面所述的来模拟，代码放着了：
#include<bits/stdc++.h>
using namespace std;
const int a2_31=2147483647;
struct node{
int v,w;
};
vector<node> a[100005];
int cnt[100005],sum;
int n,m,s;
bool f[100005];
void bfs(){
memset(cnt,0x3f,sizeof(cnt));
queue<int> q;
q.push(s);
cnt[s]=0;
f[s]=1;
while(!q.empty()){
int t=q.front();
q.pop();
f[t]=0;
for(auto i:a[t]){
if(cnt[i.v]>cnt[t]+i.w){
cnt[i.v]=cnt[t]+i.w;
if(!f[i.v]){
q.push(i.v);
f[i.v]=1;
}
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x].push_back({y,z});
}
bfs();
for(int i=1;i<=n;i++){
if(cnt[i]>1e9) cout<<2147483647<<" ";
else cout<<cnt[i]<<" ";
}
return 0;
}其实没有什么可以讲的了。
P3385 【模板】负环：
对于这道题，我们要明白，如果一个点被松弛了 n 次时，存在负环。为什么呢？因为每一个点最多直接或间接只能松弛 1 次，所以如果被松弛了 n 次，那么就存在负环，其他的就没有什么可以改变的了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int v,w;
};
vector<node> g[2005];
int a[2005],cnt[2005];
bool f[2005];
int n,m;
string SPFA(){
queue<int> q;
for(int i=1;i<=n;i++) a[i]=1e9;
memset(f,0,sizeof(f));
memset(cnt,0,sizeof(cnt));
a[1]=0;
q.push(1);
while(!q.empty()){
int t=q.front();
q.pop();
f[t]=0;
for(auto i:g[t]){
if(a[i.v]>a[t]+i.w){
a[i.v]=a[t]+i.w;
cnt[i.v]=cnt[t]+1;
if(cnt[i.v]>=n) return "YES\n";
if(!f[i.v]){
f[i.v]=1;
q.push(i.v);
}
}
}
}
return "NO\n";
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
g[u].push_back({v,w});
if(w>=0) g[v].push_back({u,w});
}
cout<<SPFA();
}
return 0;
}快快去 A 了吧。
后话：
历时一个月，如果觉得好的话就请点个赞，并留言 Clyyds，谢谢。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
