首页 > 学院 > 开发设计 > 正文

SPFA算法

2019-11-14 08:53:51
字体:
来源:转载
供稿:网友
/*由于Bellman-Ford算法的每轮操作都需要操作所有的边,显然这其中会有大量无意义的操作,严重影响了算法的性能。于是注意到,只有当某个顶点u的d[u]值改变时,从它出发的边的邻接点v的d[v]值才有可能改变。由此可以进行一个优化:建立一个队列,每次将队首顶点取出,然后对从u出发的所有边u->v进行松弛操作,也就是判断d[u]+length[u->v]<d[v]是否成立,如果成立,则用d[u]+length[u->v]覆盖d[v],于是d[v]获得更优的值,此时如果v不在队列中,就把v加入队列。这样操作直到队列为空(说明图中没有从源点可达的负环),或某个顶点的入队次数超过V-1(说明图中存在从原点可达的负环)。以下是伪代码:queue<int> Q;源点s入队;while(队列非空){	取出队首元素u;	for(u的所有邻接边u->v)	{		if(d[u]+dis<d[v])		{			d[v] = d[u] + dis;			if(v当前不在队列)			{				v入队;				if(v入队次数大于n-1)				{					说明有可达负环,return;				}			}		}	}}这种优化后的算法被称为SPFA(Shortest Path Faster Algorithm),期望时间复杂度为O(kE),k为常数,很多情况下不超过2,经常性优于堆优化的Dijkstra算法。若原图中存在从源点可达的负环则SPFA的时间复杂度会退化成O(VE)。*///下面是邻接表形式的图的SPFA代码#include<vector>#include<queue>#include<algorithm>using namespace std;const int MAXV = 1000;const int INF = 1000000000;struct Node{	int v, dis;};vector<Node> Adj[MAXV];//图G的邻接表int n, d[MAXV], num[MAXV];//num数组记录顶点的入队次数bool inq[MAXV];//顶点是否在队列中bool SPFA(int s){	//初始化部分	memset(inq, false, sizeof(inq));	memset(num, 0, sizeof(num));	fill(d, d + MAXV, INF);	//源点入队部分	queue<int>Q;	Q.push(s);//源点入队	inq[s] = true;//源点已入队	num[s]++;//源点入队次数加1	d[s] = 0;//源点的d值为0	//主体部分	while (!Q.empty())	{		int u = Q.front();//队首顶点编号为u		Q.pop();//出队		inq[u] = false;//设置u为不在队列中		//遍历u的所有邻接边v		for (int j = 0; j < Adj[u].size(); j++)		{			int v = Adj[u][j].v;			int dis = Adj[u][j].dis;			//松弛操作			if(d[u]+dis<d[v])			{				d[v] = d[u] + dis;				if (!inq[v])//如果v不在队列中				{					Q.push(v);//v入队					inq[v] = true;//设置v为在队列中					num[v]++;//v的入队次数加1					if (num[v] >= n) return false;//有可达负环				}			}		}	}	return true;//无可达环}/*注意上述SPFA代码是BFS版本,当然也可以将队列换成栈以实现DFS版本的SPFA,对判环有奇效。还有,可以将队列换成优先队列以加快速度。当然还可以换成deque(双端队列),使用SLF或LLL优化。SPFA算法有两个优化算法 SLF 和 LLL: SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,否则插入队尾。 LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。*/
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表