SPFA算法的实现：
BFS版SPFA基本算法实现：
利用一个队列来保存待优化的结点，优化时每次取出队首结点u，并用u点当前的最短路估计值对u点所指向的结点v进行松弛操作，如果结点v不在当前队列中，就将v点放入队尾。这样不断从队首取出结点进行松弛操作，直到队列为空，这样所有的松弛操作都已经结束，对最短路的求解也结束了，因为已经没有结点可以更新距离了，自然求完最短路了。
SPFA算法应用：
求解单源最短路/最长路。
BFS版SPFA求负环：
如果某一个结点的入队次数超过n次，则存在负环。因为如果图中存在负环，那么一个结点肯定会重复入队超过n次的。
void Spfa(int s) { flag=false; for(int i=0;i<maxn;i++) dis[i]=2e18; memset(vis,0,sizeof(vis)); dis[s]=0,cont[s]=1; queue<int>q; q.push(s); while(q.size()) { int u=q.front();q.pop(); for(int i=head[u];i;i=p[i].nxt) { int v=p[i].to; if(dis[v]>dis[u]+p[i].val) { dis[v]=dis[u]+p[i].val; cont[v]++; if(cont[v]>=n) { flag=true; break; } q.push(v); } } } }
#10086. 「一本通 3.3 练习 3」Easy SSSP：https://loj.ac/problem/10086
解题思路：模板题，直接用SPFA判负环并求解最短路，但是因为题目中要判断图中是否存在负权回路，并不一定要将源点S包括在负环中，所以每个点都跑一次BFS版的SPFA，最后再从源点跑一次求最短距离。
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long #define INF 0x7ffffff #define maxn 1009 #define maxm 100009 inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();} return x*f; } bool vis[maxn]; bool flag; int head[maxn],cont[maxn]; ll dis[maxn]; struct edge { int to,nxt; ll val; }p[maxm]; int n,m,k,ans,tot,cnt,s; void add(int x,int y,ll z) { ++cnt,p[cnt].to=y,p[cnt].nxt=head[x],head[x]=cnt,p[cnt].val=z; } void Spfa(int s) { flag=false; for(int i=0;i<maxn;i++) dis[i]=2e18; memset(vis,0,sizeof(vis)); dis[s]=0,cont[s]=1; queue<int>q; q.push(s); while(q.size()) { int u=q.front();q.pop(); for(int i=head[u];i;i=p[i].nxt) { int v=p[i].to; if(dis[v]>dis[u]+p[i].val) { dis[v]=dis[u]+p[i].val; cont[v]++; if(cont[v]>=n) { flag=true; break; } q.push(v); } } } } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read(),m=read(),s=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); ll z=read(); add(x,y,z); if(x==y&&z<0) flag=true; } for(int i=1;i<=n;i++) if(!cont[i]) Spfa(i); if(flag) { printf("-1"); return 0; } Spfa(s); for(int i=1;i<=n;i++) { if(dis[i]==2e18) puts("NoPath"); else printf(i==n?"%lld":"%lld ",dis[i]); } fclose(stdin); fclose(stdout); return 0; }
DFS版SPFA求负环：
在BFS版的SPFA中用一个循环的队列来保存需要继续迭代的结点，每一次扩展出一个新的节点必然放到队列的队尾，这样就中断了迭代的连续性，不可以一直迭代下去。但是如果如果采用dfs的思想，每次便可以直接从新结点继续往下扩展。
DFS对于负环的判断条件更为简单，因为假如存在负环，那么肯定会由一个点出发，最后又回到了这个店，所以只需要判断是否已经在栈中，也就是是否被访问过，但是由于图可能本来就是多个联通快，即不连通，所以每个点都要做一次。
#10084. 「一本通 3.3 练习 1」最小圈：https://loj.ac/problem/10084