关于SPFA

· · 个人记录

1 关于SPFA

它死了

SPFA大型翻车现场↑

咳咳

正经点写篇科普

1 | 1 SPFA是什么

SPFA

简单来讲，就是在图里从 一个点 到其他任意一点的一种玄学算法

并且它可以处理负权边qwq

还能判断负权环

哇哇哇是不是很棒？

至于时间复杂度嘛……（逃）

2 它死了

这就是他的玄学所在，我们稍后再细细道来哇。

2 | 1 运作方式

  1. 定义一个队列，把源点加入队列
  2. 取出队首元素点X
  3. 用X点当前的F值更新所有它能到达的点y
  4. 若y点的F值被更新，并且y并没有加入队列，那么把他放入队尾
  5. 重复2，3，4直到队列空了为止

2 | 2 代码

void spfa(){
　　memset(f,0x3f,sizeof(f));
　　memset(v,0,sizeof(v));
　　queue<int> q;//#include<queue>
　　q.push(1);
　　f[1]=0;
　　v[1]=1;
　　while(q.size()){    //while( !q.empty() )
　　　　int x,y;
　　　　x=q.front();
　　　　q.pop();
　　　　v[x]=0;
　　　　for(int i=head[x] ; i ; i=next[i])//链式前向星
　　　　　　if( f[ y=to[i] ] > f[x] + val[ i ]){
　　　　　　　　f[y]=f[x]+val[i];
　　　　　　　　if(v[y]==0) q.push(y);
　　　　　　　　　　v[y]=1;
　　　　　　}
　　}
}

2 | 3 玄学的时间复杂度

在这个算法的提出者段凡丁的论文中，他证明的时间复杂度是O(kE)，k是小常数

\colorbox{yellow}{\color{black}\text{但是（划重点）}}

最差的情况会被卡成傻逼O(VE)

妈耶想想都大

所以它才翻车了。

2 | 4 例题

洛谷\mathcal{SPFA}题目第一面

洛谷\mathbb{SPFA}题第二面