浅谈$$SPFA$$判负环

1. 关于$$SPFA$$：它死了

​ $$SPFA(Shortest Path Faster Algorithm)$$是一种优秀的单源最短路算法。它可以在$$O(km)$$的时间复杂度内求出单源最短路。

​ 但同时，$$SPFA$$有一个令人诟病的点，就是可以被特殊数据卡为$$O(n^2)$$，所以我们一般会选择更稳定的堆优化$$Dijkstra$$。但$$Dijkstra$$无法处理负权边与负环，这时候我们就需要采用$$SPFA$$

---

2.$$SPFA$$判负环的原理

​ $$SPFA$$的本质是利用队列，重复松弛节点，来求最短路径。它更像是一个能够使节点重复入队的$$BFS$$。而\(BFS\)的搜索树的深度最大不会超过节点数。而\(SPFA\)同理。

​ 设\(cnt[i]\)表示从\(1\)到\(x\)的最短路包含的边数。当执行更新\(dist[y]=dist[x]+z\)时，同时更新\(cnt[y]=cnt[x]+1\)，此时若发现\(cnt[y]>=n\)，则该图中有负环。

​ 另一种方式是记录每个点入队的次数，次数到达n时说明有负环。这种判定方式效率一般不如上面的高。

---

代码如下：

洛谷\(P3385\)

#include<bits/stdc++.h>
using namespace std;
#define maxn 60100
int head[maxn],nxt[maxn],to[maxn],tot=0;
int val[maxn];
void add(int x,int y,int z)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	val[tot]=z;
	head[x]=tot;
}
void init()
{
	memset(head,0,sizeof(head));
	memset(nxt,0,sizeof(nxt));
	memset(to,0,sizeof(to));
	tot=0;
	memset(val,0,sizeof(val));
}
int dis[maxn],inq[maxn],cnt[maxn];
int n,m;
bool spfa(int s)
{
	queue<int> q;
	q.push(s);
	memset(inq,0,sizeof(inq));
	memset(cnt,0,sizeof(cnt));
	inq[s]=1;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inq[x]=0;
		for(int i=head[x];i;i=nxt[i])
		{
			int y=to[i];
			if(dis[y]>dis[x]+val[i])
			{
				dis[y]=dis[x]+val[i];
				cnt[y]=cnt[x]+1;
				if(cnt[y]>n+1)
				return 0;
				if(!inq[y])
				{
					q.push(y);
					inq[y]=1;
				}	
				
			}
		}
	}
	return 1;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		init();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			if(z>=0)
			add(y,x,z);
		}
		
		if(spfa(1))
		printf("NO\n");
		else 
		printf("YES\n");
		
	}	
	return 0;
}