引入

SPFA的核心思想是优化dist[a]=min(dist[a],dist[b]+w)这个式子；

不难想到，如果我们想要优化dist[a]，那么只能从dist[b]+w这个式子转移过来；

也就是说，只有dist[b]变小了，才有可能优化dist[a]；

---

即只有一个点被更新过后，我们才拿这个点更新其他点；

基于这个思想，我们来实现SPFA；

注意

带有负边权的图只能用SPFA

时间复杂度

一般为$O(kE)，k是常数$；

最坏情况下是$O(VE)$

例题

SPFA求最短路

题面

传送门

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;typedef long long ll;const int N = 1e5 + 10;struct Edge{int next,to,w;
}e[N];int n,m,head[N],dist[N],cnt;bool st[N]; //判断某个点是否在队列中void add(int u,int v,int w){e[++cnt].to = v;e[cnt].next = head[u];e[cnt].w = w;head[u] = cnt;
}
int spfa(){memset(dist,0x3f,sizeof dist);queue<int> que;que.push(1);dist[1] = 0;st[1] = 1; //在队列中while(!que.empty()){auto u = que.front();que.pop();st[u] = false;//不在队列中了for(int i=head[u];i;i=e[i].next){int to = e[i].to;if(dist[to] > dist[u] + e[i].w){dist[to] = dist[u] + e[i].w;//避免重复入队if(!st[to]){que.push(to);st[to] = 1;}}}}return dist[n];
}
void solve(){cin >> n >> m;for(int i=1,u,v,w;i<=m;++i){cin >> u >> v >> w;add(u,v,w);}int ret = spfa();if(ret == 0x3f3f3f3f){cout << "impossible\n";}else cout << ret << '\n';
}int main(){std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);solve();return 0;
}

SPFA求负环

题面

传送门

思路

维护两个数组；

$dist(i)$表示起点到$i$的最短距离；
$cnt(i)$表示最短距离经过的边数；

当$cnt(i)\ge n,n$为点的数量，那么说明至少经过了$n+1$个点，也就是说出现环了；

而SPFA每次更新都只在dist变小的时候；

那么现在出现环了，且又变小了；

那么肯定就是负环;

---

注意

因为题目没有让我们维护最短路，因此我们只需要维护一个相对值即可；

而且题目只说存不存在负环，并没有指明具体哪个点开始；

因此我们在初始的时候将所有点纳入队列；

---

注意，SPFA判断负环的时间复杂度是很高的；

比如这题就跑了633ms；

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;typedef long long ll;const int N = 1e5 + 10;struct Edge{int next,to,w;
}e[N];int n,m,head[N],dist[N],tot,cnt[N];bool st[N]; //判断某个点是否在队列中void add(int u,int v,int w){e[++tot].to = v;e[tot].next = head[u];e[tot].w = w;head[u] = tot;
}
int spfa(){queue<int> que;for(int i=1;i<=n;++i){que.push(i);st[i] = 1;}while(!que.empty()){auto u = que.front();que.pop();st[u] = false;//不在队列中了for(int i=head[u];i;i=e[i].next){int to = e[i].to;if(dist[to] > dist[u] + e[i].w){dist[to] = dist[u] + e[i].w;//只多了一条 u -> v的边cnt[to] = cnt[u] + 1;if(cnt[to] >= n) return true;//避免重复入队if(!st[to]) que.push(to);}}}return false;
}
void solve(){cin >> n >> m;for(int i=1,u,v,w;i<=m;++i){cin >> u >> v >> w;add(u,v,w);}bool ret = spfa();if(ret){cout << "Yes\n";}else cout << "No\n";
}int main(){std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);solve();return 0;
}