SPFA算法深度探究

SPFA??它已经死了,完结撒花~~

图论里面有一个致命的东西,那就是负权边,现在我会的算法中能解决负边的只有$O(n^3)$的$Floyd$……遇到负权边我们还是要向死了的SPFA伸手


↑↑正文分割线

  • SPFA说的牛逼一点就是$(Shortest$ $Path$ $Faster$ $Algorithm)$,说的谦虚(全球化)一点就是队列优化的$Bellman-Ford$算法。那么这个$Bellman-Ford$又是什么东西呢??

$Bellman-Ford$算法

  • 我在寒假集训Day1的笔记里曾提到这个东西,松弛:$dis[v]=\min⁡(dis[v],dis[u]+dis(u,v))$

    • 核心代码:
    1
    2
    3
    4
    for (int k=1;k<=n-1;k++)//n是顶点的数量
    for (itn i=1;i<=m;i++)//m是边的数量
    if (dis[v[i]]>dis[u[i]]+w[i])//u[i]和v[i]是边的两个顶点
    dis[v[i]]=dis[u[i]]+w[i];//w[i]是边的费用
    • 分析:首先,为什么要进行$n-1$次呢??因为在$n$个顶点的图中,任意两点的最短路最多包含$n-1$条边。这样算下来,时间复杂度是$O(nm)$,当然还可以优化(不是SPFA),可以发现我们常常在$n-1$次循环以前就完成了所有松弛,如果发现某次松弛没有发生变化,即可提前跳出循环。
  • 判断负权边:进行$n-1​$次松弛后再来一次松弛,如果答案还有变化,说明有负权边。

$SPFA$算法

  • 同上,我曾经在同一篇文章上写过,但是人的本质是复读机,所以…….
  • 算法:每次选取队首顶点$u$,对顶点$u$的所有出边进行松弛。如果有一条$u$→$v$的边可以使源点到$v$的距离变短,就把$v$放加入队尾。细心的你一定会发现,同一个顶点在队列中出现多次是没有意义的,所以再开一个数组来判重就可以了。对顶点$u$的所有出边松弛完后,就让$u$出队。如此反复,知道队列空,是不是很像$bfs$??
  • Code:@codesonic dalao的模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <queue>
using namespace std;

const int inf=2147483647;
const int maxn=10005;
int n,m,b,e=0,i,j;
int dis[maxn],head[500005];
bool vis[maxn];
struct node
{
int next,to,dis;
}edge[500005];

queue<int> q;
void addedge(int from,int to,int dis)
{
edge[++e].next=head[from];
edge[e].dis=dis;
edge[e].to=to;
head[from]=e;
}

void spfa()
{
for(i=1;i<=n;i++) dis[i]=inf;
dis[b]=0;
q.push(b),vis[b]=1;
while(!q.empty())
{
int begin=q.front();
q.pop();
for(i=head[begin];i;i=edge[i].next)
{
if(dis[edge[i].to]>dis[begin]+edge[i].dis)
{
dis[edge[i].to]=dis[begin]+edge[i].dis;
if(!vis[edge[i].to])
{
vis[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
vis[begin]=0;
}
}
int main()
{
cin>>n>>m>>b;
for(int i=1; i<=m; i++)
{
int f,t,d;
cin>>f>>t>>d;
addedge(f,t,d);
}
spfa();
for(int i=1; i<=n; i++)
if(b==i) cout<<0<<' ';
else cout<<dis[i]<<' ';
return 0;
}
  • 但是,众所周知,$SPFA$是会被毒瘤出题人卡的,最坏复杂度也是$O(nm)$,所以如果没有负权边的话,最好还是用$Dijkstra$,复杂度$O((M+N) \log N)$。

SPFA的其他优化

咕咕咕……(等待更新QAQ)更新分割线↓↓↓


  • 上面提到过,原始的$SPFA$有$bfs$的思想,所以每次遇到负边的时候,复杂度就会降为$O(nm)$,所以针对这个问题,可以使用$dfs$版的$SPFA$,直接从新节点开始往下递归。判断负环也更为简单,如果存在$a_1 \Rightarrow a_2 \Rightarrow a_3 \Rightarrow …. \Rightarrow a_k \Rightarrow a_1$,那么就可以确定这是一个环,所以只要用一个数组来记录一个结点是否在递归栈中就可以了~~
  • 伪代码:
1
2
3
4
5
6
7
8
9
10
11
12
Void SPFA(Node){
Instack[Node]=true;
For (NOde,v) ∈ E
If dis[Node]+edge(Node,v)<dis[v] then{
dis[v]=dis[Node]+edge(Node,v);
If not Instack[v] then
SPFA();
Else
Return;
}
Instack[Node]=false;
}

基于dfs的SPFA相关优化

咕咕咕…..(等待更新)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×