spfa学习笔记

目录

• 1.引言
• 2.算法详解
• 3.例题&代码
• 4.心得

引言

今天为了练链式前向星，写了一道橙题，然后看到 \(n \le 100\) 的数据量，毅然选择了使用SLF优化的SPFA求解（没错就是spfa。然而，前途是光明的，路途是坎坷的。折磨开始了……在历经4个小时的自学后，我学成归来解决了那道橙题，为了避免今天学了明天忘，记下这篇学习笔记。

2.算法详解

算法思想：我们用数组 \(d\) 记录每个结点的最短路径估计值，用邻接表来存储图 \(G\)。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点 \(u\) ，并且用u点当前的最短路径估计值对离开 \(u\) 点所指向的结点 \(v\) 进行松弛操作，如果 \(v\) 点的最短路径估计值有所调整，且 \(v\) 点不在当前的队列中，就将 \(v\) 点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

期望的时间复杂度 \(O(ke)\)， 其中 \(k\) 为所有顶点进队的平均次数，可以证明 \(k\) 一般小于等于 \(2\)。

实现方法：

　　建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为 \(0\) 。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

关于优化：

SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表]
是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。

判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。

SLF 策略，设要加入的节点是 \(j\)，队首元素为 \(i\)，若 \(dist(j)<dist(i)\)，则将 \(j\) 插入队首，否则插入队尾。

例题&代码

洛谷P3905

没啥好讲解的，主要就是链式前向星存储图，邻接矩阵存储两点之间的路的好坏关系，然后在松弛边的时候若b[u][v]为false就用三目运算符返回w[i]，否则返回 \(0\)。（注意：道路是无权图，连边和存储好坏关系时正反存一次）

参考代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<deque>
using namespace std;
const int maxn = 107,inf=0x3f3f3f3f;
int idx;
bool vis[5*maxn];
int v[5*maxn],w[5*maxn],to[5*maxn],head[5*maxn],dis[5*maxn];
bool b[maxn][maxn];
void add(int u, int vi, int wi) {
	v[++idx]=vi;
	w[idx]=wi;
	to[idx]=head[u];
	head[u]=idx;
}
void spfa(int s,int n) {
	deque<int>q;
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	q.push_back(s);
	vis[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u]; i>-1; i=to[i]) {
			int vi=v[i];
			if(dis[vi]>dis[u]+(b[u][vi]?0:w[i])) {
				dis[vi]=dis[u]+(b[u][vi]?0:w[i]);
				if(!vis[vi]) {
					vis[vi]=1;
					if(!q.empty()&&dis[vi]<dis[q.front()])q.push_front(vi);
					else q.push_back(vi);
				}
			}
		}
	}
}
int main() {
	memset(head, -1, sizeof(head));
	memset(b, 1, sizeof(b));
	int n,m,d,A,B;
	cin >>n>>m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	cin>>d;
	for(int i=0; i<d; i++) {
		int u , v;
		cin >> u >> v;
		b[u][v]=b[v][u]=0;
	}
	cin>>A>>B;
	spfa(A,n);
	cout<<dis[B]<<endl;
	return 0;
}

赶快学起来吧！

心得

唉，spfa你因太强而被处处针对，所以人还是要学会敛其锋芒啊！（spfa喜诈尸