【信竞】SPFA超详解

本文章部分参考 luogu日报 WIKI

算法优点：

        1.时间复杂度比普通的Dijkstra和Ford低。

        2.能够计算负权图问题。

        3.能够判断是否有负环 (即：每跑一圈，路径会减小，所以会一直循环跑下去)。

算法过程：

实现方法：

　　1.存入图。可以使用前向星或者邻接矩阵（不推荐）。

        2.开一个队列，先将开始的节点v0放入。设数组d[i]表示目前从起点到i节点的最短路径长，注意使d[v0]=0

        3.每次从队列中取出当前节点X，并出队，遍历与X相通的Y节点，比较 d[Y] 和 d[X]的+ X到Y的边长度E(x,y)

            如果 d[X] + E(x,y)  < d[Y],说明需要更新操作：

                    1）.令 d[Y]=d[X]+E(x,y)

                    2）.由于改变了d[Y]，所以原与Y有关联的点都可能需要更新，则将Y加入队列。这个地方可以稍稍优化：(即：判断下Y是否已经在队列，在就不用重复，不在就加入队列（已经待更新了），等待更新)。

                    3）.在这期间可以记录这个节点的进队次数，用于判断是否存在负环。

        4.直到队空。

判断有无负环：如果某个点进入队列的次数超过N次则存在负环。

模拟过程

我引用下别人的博客内容

以下图解来自 http://keyblog.cn/article-21.html

http://keyblog.cn/article-21.html

首先建立起始点a到其余各点的最短路径表格

首先源点a入队，当队列非空时：

        １、队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：

在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d

队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：

在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e

队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：

在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f

 队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：

在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g

队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：

在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e

队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：

在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：

在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b

队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：

在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了

最终a到g的最短路径为１４

下面是模版代码

bool SPFA(int v0,int n)
{
	queue<int>q;//自己写时候最要好移到函数外去定义
	memset(d,127,sizeof d);
	memset(ven,0,sizeof ven);	//记录是否在数组 
	memset(nums,0,sizeof nums);	//记录入队次数 
	d[v0]=0;				//初始化距离 
	ven[v0]=1,nums[v0]++;	//标记v0点在队列，队列次数+1 
	q.push(v0);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();			//出队 
		ven[x]=0;			//标记不在队列 
		for(int i=h[x]; i; i=edge[i].next)	//遍历与x节点连通的点 
		{
			int y=edge[i].y;				//节点y 
			if(d[x]+edge[i].v<d[y])		//更新 
			{
				d[y]=d[x]+edge[i].v;
				if(!ven[y])
				//由于更新了节点，所以后续以这个为基础的最短路，也要更新下
				//所以如果在队列就不用加入（已经待更新），不在的话加入更新后续节点
				{
					q.push(y);
					ven[y]=1;		//标记这个节点在队列中 
					nums[y]++;		//记录加入次数 
					if(nums[y]>n)	//如果这个点加入超过n次，说明存在负圈，直接返回 
						return 0;
				}
			}
		}
	}
	return 1;
}

优化（卡常）技巧

SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。

有两种可用的技巧可以用来提升队列的质量，并且借此能够提高平均性能（但仍无法提高最坏情况下的性能，但可能可以避免一些情况下的被卡）。

1. 距离小者优先

用这个法子的话，那么队列要用双端队列（deque或手工模拟）

将总是把y压入队列尾端修改为比较d[y]与d[q.front()]（队列头端元素的d）若d[y] < d[q.front()] 则压入队列头端（q.push_front(y)）。

if(d[x]+edge[i].v<d[y])      //松弛操作修改 (此外改队列为deque)
{
	d[y]=d[x]+edge[i].v;
	if(!ven[y])
	{
		if(d[y]<q.front())
			q.push_front(y);
		else
			q.push_back(y);
		ven[y]=1;    
		nums[y]++;
		if(nums[y]>n)
			return 0;
	}
}

2. 距离大者置后

对每个要出对的元素x，比较d[x]和队列中d的平均值，如果d[x]更大，那么将它弹出放到队尾，取队首元素在进行重复判断，直至存在d[x]小于平均值

这两种优化可以同时用。我就讲到这里了。以后有什么再改改吧。

更多的可以参见 http://www.360doc.com/content/19/0107/07/5315_807139937.shtml