算法导论——spfa
Victory_Defeat
2018-08-18 17:16:59
虽然**spfa已经死了**，但是**毕竟不是所有题目都没有负权值啊**，再说了**万一明年NOI出题人卡dijkstra呢？**~~（滑稽）~~
下面介绍一下spfa**思路**：
首先**将起点入队**，并**将距离置为$0$，标记为使用过**，其他的点**初始距离为$INF$，标记为未使用**
然后只要**队列不为空（还有点未计算过）**，就继续操作：
先**取出队首元素**，然后**枚举与它相邻的边**，如果**该边连着的另一点未使用且这种走法更优，则将该点入队并更新距离和使用与否**
这样操作**时间复杂度约是$O \left( kE \right )$，一般$k \leq 2$**，**但是在最坏情况下可能退化至$O \left ( VE \right )$**，虽然很多人都知道这一点，但是**这是为什么呢**？
首先，我们都知道一个点**如果入队$\geq V$次，那么这个图必有负环**，所以一个无负环的图中一个点**最多入队$V-1$次**，则**时间复杂度为$O \left ( \left ( V-1 \right )E \right )$，而由于一般情况下不考虑指数低的项，故时间复杂度为$O \left ( VE \right )$，证毕。**
上面是关于spfa**思路和时间复杂度的证明**，下面就~~直接上代码吧~~**来将spfa与dijkstra进行对比**：
1. **使用范围**：
spfa：**判负环或无负环的最短路**
dijkstra：**无负权的最短路**
2. **优化前时间复杂度**：
spfa：**平均$O \left( kE \right )$，最坏$O \left ( VE \right )$**
dijkstra：**$O \left ( n^2 \right )$**
3. **优化后时间复杂度**：
spfa：**大概$O \left( kE \right )$（$k \thickapprox 0.8$）**
dijkstra：**$O \left( n\ log\ n \right )$**
最后才是**上代码！！！**
```cpp
#include<cstdio>
#include<queue>
#define inf 2147483647
using namespace std;
struct Edge
{
int next,to,dis;
}edge[600000];
bool f[20000];
int a[20000],head[600000],num,n,m,s;
void ins(int p,int q,int v)
{
edge[++num].next=head[p];
edge[num].to=q;
edge[num].dis=v;
head[p]=num;
}
void spfa()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
a[i]=inf;
f[i]=0;
}
a[s]=0;
f[s]=1;
q.push(s);
while(!q.empty())
{
int t=q.front();
q.pop();
for(int i=head[t];i;i=edge[i].next)
{
int u=edge[i].to;
if(a[u]>a[t]+edge[i].dis)
{
a[u]=a[t]+edge[i].dis;
if(!f[u])
{
f[u]=1;
q.push(u);
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int p,q,v;
scanf("%d%d%d",&p,&q,&v);
ins(p,q,v);
}
spfa();
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
```