博客

为什么能够判负环？根据原理，每个最短路都不会超过n-1条边，如果说超过了n-1条边的话，那么就说明走了重点，即走了环，因此就可以知道里面产生了负环，才使得这个最短路无解。

SPFA对这个算法很好地进行了优化。

优化的根源在于，能够改变最短路的路径都是之前成功松弛过的点，也就是说，如果一个点被成功地松弛了，那么这个点才有可能松弛其它边，没有被松弛的点，就说明这个点所记录的最短路径没有改变，那么以这个点为起点的边都不可能被松弛，所以具体的实现就是造一个队列，把成功松弛的点放入队列之中等待松弛，知道队列中没有点了，说明整个最短路的过程就结束了。

一个点如果被松弛了N次，就说明产生了负环。

int head[MAXN],next[MAXN],dis[MAXN]; 
bool vis[MAXN];
struct node{
	int u,v,c;
	node(){}
	node(int u,int v,int c){
		this->u=u; this->v=v; this->c=c;
	}
}p[MAXN];
int e,n,m;
int cnt[MAXN];
void addnode(int u,int v,int c){
	p[e]=node(u,v,c);
	next[e]=head[u]; head[u]=e++;//head[i]表示节点i的第一条边的标号，next[e]表示第e条边的下一条边的编号。
}
bool relax(int u,int v,int c){
	if(dis[v]>dis[u]+c){
		dis[v]=dis[u]+c;
		return true;
	}
	return false;
}
void init(){
	memset(head,-1,sizeof(head));
	memset(next,-1,sizeof(next));
	e=0;
	for(int i=0;i<m;i++){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		addnode(u,v,c);
		//addnode(v,u,c);反向边 
	}
}
bool spfa(int src){
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++){
		dis[i]=INF;
	}
	dis[src]=0; vis[src]=true;
	queue<int>que; que.push(src);
	while(que.size()){
		int now=que.front(); que.pop();
		vis[now]=false;//出队后取消标记 
		for(int i=head[now];i!=-1;i=next[i]){
			if(relax(now,p[i].v,p[i].c)&&!vis[p[i].v]){//标记必须写在松弛之后，不然无法松弛以在队列内的点
				if((++cnt[p[i].v])>n) return false;//一个点如果被松弛了n次，说明产生了负环 
				que.push(p[i].v);
				vis[p[i].v]=true;
			}
		}
	}
	return true;
}