SPFA 算法

博主：摸鱼酱
发布时间：2020 年 02 月 03 日
1122次浏览
4 条评论
2120字数
分类： OI之路

# 前言

SPFA，全名 Shortest-Path-Faster-Algorithm，是 Bellman-Ford 算法的一种队列优化版本。通常用于求含负权边的单源最短路径，以及判负权环。

但这种算法一直不被国际所认可，也没有在专业的论文中被严格证明时间复杂度，所以~~部分毒瘤出题人~~会出卡 SPFA 的数据。

---

# 正文

因为是优化 Bellman 上来的，所以优化的是 Bellman 的最薄弱的地方--时间的浪费。

Bellman 花费了太多时间在没有作用的循环上，真正进行的松弛操作并不多，所以 SPFA 用一个**队列**来进行优化。以下是具体过程。

首先建立队列，里面存放待进行优化的结点，最初的元素为根节点。开一个数组记录元素是否已经在队列中。

当队列不为空时，取出队首元素 $u$，并循环枚举与 $u$ 连接的点 $v$，判断如果 $dis[v]>dis[u]+w$，即从 $u$ 走向 $v$ 比之前操作更优，那就更新 $dis[v]$ 的值。满足条件之后，如果 $v$ 不在队列中，则把它加入队列。记得添加/消除标记。

每次更新结点的 `dis[]` 值称为一次松弛操作，如果一个结点被松弛达到 $n$ 次，那么这个图中含有负权环。

SPFA 和 bfs 只有略微的差别，那就是$SPFA$中一个元素可以反复加入队列，只要它满足条件，而 bfs 不会。

稳定性不用说，稍微特殊构造数据就炸。

---

至于各种优化？比如下面列的：(摘自知乎)

> LLL 优化：每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾。

> Hack：向 1 连接一条权值巨大的边，这样 LLL 就失效了。

> SLF 优化：每次将入队结点距离和队首比较，如果更大则插入至队尾。

> Hack：使用链套菊花的方法，在链上用几个并列在一起的小边权边就能欺骗算法多次进入菊花。SLF 带容错：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。

> SLF 带容错：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。

> Hack：如果边权之和很小的话似乎没有什么很好的办法，因为令边权之和为 $W$ ，那么令容错值为 $sqrt(W)$ ，总复杂度似乎接近 $O((V+E)sqrt(W))$。我不确定这个复杂度对不对，但是 SPFA 确实在边权和小的时候跑得蛮不错的。所以卡法是卡$SLF$的做法，并开大边权，总和最好超过 $10^{12}$ 。

> mcfx 优化：在第 $[L,R]$ 次访问一个结点时，将其放入队首，否则放入队尾。通常取 $L=2,R=sqrt(V)$ 。

> Hack：网格图表现优秀，但是菊花图表现很差。P.S. 此优化与 SLF 带容错一起使用有更好的效果，可以使所需要的边权上升许多。

> SLF + swap：每当队列改变时，如果队首距离大于队尾，则交换首尾。

> Hack: 与卡 SLF 类似，外挂诱导节点即可。

---

从原理上来看，这些优化都是为了让队列更加接近优先队列，但维护一个优先队列需要至少 $\log$ 级的时间复杂度（目前来看），所以低于这个时间复杂度级别的处理...总有能卡的吧..

即使如此，SPFA 也不失为考场上随机对拍数据的一个帮手或者是时间不足时的备用方案，但如果没有紧急情况？乖乖背 dij+heap 吧。

---

update:2020.10.28 放一份 SLF 带容错 + mcfx 的板子。

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=2e6+10;
int in[N],dis[N],vis[N];
int head[M],to[M],val[M],nxt[M],cnt;
void add(int u,int v,int w){
	to[++cnt]=v,val[cnt]=w,nxt[cnt]=head[u],head[u]=cnt;
}
const int del=10;
int l,r;
void spfa(int s){
	deque<int> q;
	q.push_front(s);
	in[s]=1;vis[s]=1;dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		in[u]=0;
		q.pop_front();
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i],w=val[i];
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!in[v]){
					vis[v]++;
					in[v]=1;
					if(l<=vis[v]&&vis[v]<=r||dis[v]-del<=dis[q.front()])q.push_front(v);
					else q.push_back(v);
				}
			}
		}
	}
}
int main(){
	memset(dis,0x3f,sizeof dis);
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	l=2,r=sqrt(m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa(s);
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}
```

```

最后修改：2021 年 08 月 23 日 06 : 24 PM

4 条评论

李佳析
September 15th, 2021 at 09:29 pm

这个代码颜色很伤眼睛啊喂

回复
1. 摸鱼酱
  September 19th, 2021 at 09:27 pm
  
  @李佳析
  
  个人感觉还好啊，有很不舒服吗
  
  回复
www
April 22nd, 2021 at 05:05 pm

fuckme

回复
Quacky
February 15th, 2020 at 10:36 am

1+9=10

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱

地址

SPFA 算法

摸鱼酱 • 2020 年 02 月 03 日

# 前言

SPFA，全名 Shortest-Path-Faster-Algorithm，是 Bellman-Ford 算法的一种队列优化版本。通常用于求含负权边的单源最短路径，以及判负权环。

但这种算法一直不被国际所认可，也没有在专业的论文中被严格证明时间复杂度，所以~~部分毒瘤出题人~~会出卡 SPFA 的数据。

---

# 正文

因为是优化 Bellman 上来的，所以优化的是 Bellman 的最薄弱的地方--时间的浪费。

Bellman 花费了太多时间在没有作用的循环上，真正进行的松弛操作并不多，所以 SPFA 用一个**队列**来进行优化。以下是具体过程。

首先建立队列，里面存放待进行优化的结点，最初的元素为根节点。开一个数组记录元素是否已经在队列中。

每次更新结点的 `dis[]` 值称为一次松弛操作，如果一个结点被松弛达到 $n$ 次，那么这个图中含有负权环。

SPFA 和 bfs 只有略微的差别，那就是$SPFA$中一个元素可以反复加入队列，只要它满足条件，而 bfs 不会。

稳定性不用说，稍微特殊构造数据就炸。

---

至于各种优化？比如下面列的：(摘自知乎)

> LLL 优化：每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾。

> Hack：向 1 连接一条权值巨大的边，这样 LLL 就失效了。

> SLF 优化：每次将入队结点距离和队首比较，如果更大则插入至队尾。

> SLF 带容错：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。

> mcfx 优化：在第 $[L,R]$ 次访问一个结点时，将其放入队首，否则放入队尾。通常取 $L=2,R=sqrt(V)$ 。

> Hack：网格图表现优秀，但是菊花图表现很差。P.S. 此优化与 SLF 带容错一起使用有更好的效果，可以使所需要的边权上升许多。

> SLF + swap：每当队列改变时，如果队首距离大于队尾，则交换首尾。

> Hack: 与卡 SLF 类似，外挂诱导节点即可。

---

即使如此，SPFA 也不失为考场上随机对拍数据的一个帮手或者是时间不足时的备用方案，但如果没有紧急情况？乖乖背 dij+heap 吧。

---

update:2020.10.28 放一份 SLF 带容错 + mcfx 的板子。

```

4 条评论

发表评论 取消回复

SPFA 算法

发表评论取消回复