单源最短路之SPFA——Shortest Path Faster Algorithm

   SPFA是目前相当优秀的求最短路径的算法，值得我们掌握。
   SPFA对Bellman-Ford算法优化的关键之处在于意识到：只有那些在前一遍松弛中改变了距离估计值的点，才可能引

起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。初始时，源点s入队。

当队列不为空时，取出对首顶点，对它的邻接点进行松弛。如果某个邻接点松弛成功，且该邻接点不在队列中，则将其

入队。经过有限次的松弛操作后，队列将为空，算法结束。SPFA算法的实现，需要用到一个先进先出的队列 queue 和

一个指示顶点是否在队列中的 标记数组 mark。为了方便查找某个顶点的邻接点，图采用临界表存储。
   需要注意的是：仅当图不存在负权回路时，SPFA能正常工作。如果图存在负权回路，由于负权回路上的顶点无法收

敛，总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。
判断负权回路的方案很多，世间流传最广的是记录每个结点进队次数，超过|V|次表示有负权
关于SPFA的时间复杂度，一般认为是 O（kE），k一般为2。
如果在判断是否存在负权回路，推荐使用第一种优化形式，否则推荐使用SPFA。

 

//题目要求：判断有无负权环
#include <iostream>
using namespace std;
const int N = 502;
const int MAX = INT_MAX;
int f;
int n;					//节点个数为n，边数为2*m+w
int m;
int w;
int queue[N],time[N],dis[N];	//循环队列，记录每个节点入队列的次数（大于n表示有负权环），dis记录最短路径值
bool vis[N];			//true表示在队列中。被松弛的点若在队列中，就不加入队列，出队列后值为false
int pre[N];			//节点i发出若干条边，pre[i]表示节点i当前正在遍历的边的前一条边的序号
typedef struct
{
	int to;
	int w;
	int next;
}Edge;
Edge e[5201];

bool spfa()
{
	int i,j,now,adj;
	memset(vis,false,sizeof(vis));
	memset(time,0,sizeof(time));
	for(i = 2, dis[1] = 0; i <= n; i++)
		dis[i] = MAX;
	queue[0] = 1;
	vis[1] = true;
	time[1] = 1;
	int head = 0,tail = 1;
	while(head != tail)
	{
		now = queue[head];
		head = (head + 1) % n;
		vis[now] = false;
		for(i = pre[now]; i != -1; i = e[i].next)
		{
			adj = e[i].to;
			if(dis[now] != MAX && dis[now] + e[i].w < dis[adj])
			{
				if(adj == 1)		//若初始点1本身包含负环，直接返回
					return true;
				dis[adj] = dis[now] + e[i].w;
				if(!vis[adj])
				{
					queue[tail] = adj;
					tail = (tail + 1) % n;
					vis[adj] = true;
					time[adj] ++;
					if(time[adj] > n)
						return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	int i,j,edgeNum;
	int from,to,w1;
	cin>>f;
	for(i = 0; i < f; i++)
	{
		edgeNum = 0;
		memset(pre,-1,sizeof(pre));
		memset(e,0,sizeof(e));
		cin>>n>>m>>w;
		for(j = 1; j <= m; j++)
		{
			cin>>from>>to>>w1;
			e[edgeNum].to = to; e[edgeNum].w = w1; e[edgeNum].next = pre[from];
			pre[from] = edgeNum;
			edgeNum++;
			e[edgeNum].to = from; e[edgeNum].w = w1; e[edgeNum].next = pre[to];
			pre[to] = edgeNum;
			edgeNum++;
		}
		for(j = 1; j <= w; j++)
		{
			cin>>from>>to>>w1;
			e[edgeNum].to = to; e[edgeNum].w = -w1; e[edgeNum].next = pre[from];
			pre[from] = edgeNum;
			edgeNum++;
		}
		if(spfa())
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}

    

    参见poj3259,1511