浅谈 SPFA
## 前言：
大家好，我是 Clare613，今天和大家好好唠一唠 SPFA。
## SPFA 算法简介：
### 何为 SPFA：
SPFA 算法是 Bellman-Ford 算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。
### 有什么用：
SPFA 作为最基础的单源最短路，个人认为类似于 BFS，代码大概是这样的：
```cpp
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 的基础题，按照前面所述的来模拟，代码放着了：
```cpp
#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 次，那么就存在负环，其他的就没有什么可以改变的了。
```cpp
#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，谢谢。## 前言：
大家好，我是 Clare613，今天和大家好好唠一唠 SPFA。
## SPFA 算法简介：
### 何为 SPFA：
SPFA 算法是 Bellman-Ford 算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。
### 有什么用：
SPFA 作为最基础的单源最短路，个人认为类似于 BFS，代码大概是这样的：
```cpp
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 的基础题，按照前面所述的来模拟，代码放着了：
```cpp
#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 次，那么就存在负环，其他的就没有什么可以改变的了。
```cpp
#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，谢谢。
