ACM

SPFA从入门到忘记(

SPFA 算法是Bellman-Ford算法的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。

百度百科

在图论的学习中我们常常会遇到这样一类问题:在一个给定的图中求某一个点到另一个点/其他所有点的最短路径的长度。

我们称这样的问题为单源最短路径问题

根据图的形式不同,我们用不同的算法解决这个问题。如果图中没有负边权,我们使用Dijkstra算法,否则使用SPFA算法。

SPFA算法的全称是Shortest Path Faster Algorithm,直译是快速最短路径算法。但是在OI比赛中SPFA算法早已被宣判了死刑。该算法的时间复杂度在最坏情况下是O(nm),并且非常容易被卡到O(nm)。但是目前为止能够解决带有负边权图的单源最短路径的算法中,SPFA已经是表现最好的一个了。因此我们还是有必要去学习一下这个算法。

SPFA算法脱胎于Bellman-Ford(读作贝尔曼福特)算法,是该算法的队列版本。但是鉴于Bellman-Ford并不常用,因此不作介绍。

SPFA算法的核心思想非常简单利落:循环从队列中取点,用该点为中转点去更新其他点,如果其他点被更新了就将该点入队。直到队列为空时才停止。

算法的做法和实际实现起来都非常轻松,但是其实内在原理并不简单。鉴于该算法应用范围不广,实际用到了还是抄板子,所以本文不对原理进行说明。

下面给出一道例题:luogu3371

我的代码如下:

#include<bits/stdc++.h>
using namespace std;
#define N 1000001
#define M 5000001
int hd[N],nx[M],e[M],w[M],d[N];
int n,m,x,y,z,s;
bool v[N];
void init(){
	memset(hd,0,sizeof(hd));
	memset(v,0,sizeof(v));
	memset(d,63,sizeof(d));
	scanf("%d%d%d",&n,&m,&s);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		nx[i]=hd[x],hd[x]=i,e[i]=y,w[i]=z;
	}
}
void Spfa(int s){
	queue<int> que;
	que.push(s);d[s]=0;
	while (!que.empty()){
		int x=que.front();que.pop();
		for (int i=hd[x];i;i=nx[i])
			if (d[e[i]]>d[x]+w[i]){
				d[e[i]]=d[x]+w[i];
				if (!v[e[i]]){
					que.push(e[i]);
					v[e[i]]=true;
				}
			}
		v[x]=false;
	}
}
void print(){
	for (int i=1;i<=n;i++) printf("%d ",d[i]==1061109567?2147483647:d[i]);
	printf("\n");
}
int main(){
	init();
	Spfa(s);
	print();
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注