最短路之SPFA学习笔记

发表于 | 更新于 | 评论数： | 阅读次数：

讲到SPFA，泥萌是不是都想到了luogu上传的很广的一句话：

关于SPFA，Ta死了。

先来看一下时间复杂度$O(kE)$,E是边数,k为常数，平均值为2（至于为什么我也不会证明）。

别急，在讲SPFA之前，先来看一看它的朴素算法Bellman-Ford。

Bellman-Ford

简介

时间复杂度$O(NE)$，N是顶点数，E是边数。

简称Ford算法，和Dijsktra一样，也是一种单源最短路径的算法。

能够处理负边权的情况，但无法处理负权回路的情况。

实现方式

设start为起点，dist[i]就是start到i的最短路长度。

front[i]是i的前驱，w[j]是边j的长度（j连接u、v）。

初始化:
dist[start]=0,dis[i]=inf$(i \not = start)$front[start]=0。

算法主体：

1
2
3
4
5
6
7
8
for(int i=1;i<=n-1;i++){
    for(int j=1;j<=m;j++){
        if(dist[u]+w[j]<dist[v]){
            dist[v]=dist[u]+w[j];
            front[v]=u;
        }
    }
}

SPFA

了解了Bellman-Ford之后，我们看一下它的优化SPFA算法。

SPFA算法本质上实在Bellman-Ford的基础上运用了队列优化，减少了不必要的冗余计算。

主要思想

初始时，我们将起点加入队列。

我们每次从队列中取出一个元素，并对所有与它相连的点进行修改，若某个相邻的点修改成功，则将其压入队列，直到队列为空时，程序结束。

SPFA算法在形式上很像广搜，但是不同的是广度优先搜索中一个点出现在队列中就不会出现第二次。但是SPFA中一个点可能出现在队列之后又被再次放入队列。

也就是说，一个点修改过其他点之后，过了一段时间可能会重新获得更短的路径，于是再次用来给另一个点查找，这样循环往复的进行下去。

算法实现

我们用dist[i]记录起点start到i的最短路径，front[i]记录前驱。

这里我们使用链式前向星存图，所以我们枚举每一条边时应该：

1
2
3
for(int i=head[first];i;i=node[i].next){
    ...
}

bool数组visited[i]记录一个点是否出现在队列中。

初始化：

1
2
3
for(int i=1;i<=n;i++)dist[i]=inf;
dist[start]=0;
for(int i=1;i<=n;i++)visited[i]=false;

算法主体：

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
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    dist[k]=0;
    Q.push(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        Q.pop();
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                if(!visited[node[i].to]){
                    visited[node[i].to]=true;
                    Q.push(node[i].to);
                }
            }
        }
    }
}

SPFA记录最短路径

我们用front[i]来记录点i的前驱。

在求解最短路时，我们在更新时将前驱记录下来。

在输出时，由于路径是倒序记录的，所以首先将front[i]放进一个栈里。

每次输出栈顶即可。

代码实现：

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
int front[MAXN];
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    queue<int>Q;
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    dist[k]=0;
    Q.push(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        Q.pop();
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                front[node[i].to]=first;
                if(!visited[node[i].to]){
                    visited[node[i].to]=true;
                    Q.push(node[i].to);
                }
            }
        }
    }
}
inline void print(int k){
    for(int i=0;i<m;i++){
        if(i!=k){
            int end=i;
            stack<int>s;
            cout<<"from "<<k<<" to "<<end<<":"<<endl;
            while(k!=end){
                s.push(end);
                end=front[end];
            }
            cout<<k;
            while(!s.empty()){
                cout<<"-->"<<s.top();
                s.pop();
            }
        }
    }
}

SPFA算法的优化

SPFA算法有几个小优化，虽然提升速度不大，但实际上还是有的。

SLF（Small Label First）优化

思路很简单：
我们把SPFA朴素算法时的普通搜索队列改为双端队列(deque)。

我们对于一个即将加入队列的节点u，如果dist[u]小于队首元素dist[first]，那么u就加入队首元素。

否则u则被加入队尾元素。

代码实现：

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
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    deque<int>Q;
    dist[k]=0;
    Q.push_back(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        Q.pop_front();
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                front[node[i].to]=first;
                if(!visited[node[i].to]){
                    visited[node[i].to]=true;
                    if(dist[node[i].to]<dist[Q.front()])Q.push_front(node[i].to);
                    else Q.push_back(node[i].to);
                }
            }
        }
    }
}

LLL（Large Label Last）优化

它的策略也很简单。

我们对于每一个要出队的元素u，比较一下dist[u]和当前队列里dist的平均值，如果dist[u]更大，那么将它弹出放到队尾，取队首元素进行重复判断，直到存在dist[k]小于平均值。

代码实现：

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
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    queue<int>Q;
    int cnt=k,sum=0;
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    dist[k]=0;
    Q.push(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        while(dist[first]*cnt>sum){
            Q.pop();
            Q.push(first);
            first=Q.front();
        }
        Q.pop();
        cnt--;
        sum-=dist[first];
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                if(!visited[node[i].to]){
                    sum+=dist[node[i].to];
                    cnt++;
                    Q.push(node[i].to);
                }
            }
        }
    }
}

SLF+LLL优化

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
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    deque<int>Q;
    int cnt=k,sum=0;
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    dist[k]=0;
    Q.push_back(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        while(dist[first]*cnt>sum){
            Q.pop();
            Q.push(first);
            first=Q.front();
        }
        Q.pop_front();
        cnt--;
        sum-=dist[first];
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                if(!visited[node[i].to]){
                    sum+=dist[node[i].to];
                    cnt++;
                    if(dist[node[i].to]<dist[Q.front()])Q.push_front(node[i].to);
                    else Q.push_back(node[i].to);
                }
            }
        }
    }
}

容错SLF优化

还是利用双端队列deque。

我们定义一个容错值val，当满足dist[node[i].to]>dist[Q.front]+val时，从队尾插入，否则从队首插入。

代码实现：

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
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    deque<int>Q;
    int val=k;
    dist[k]=0;
    Q.push_back(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        Q.pop_front();
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                front[node[i].to]=first;
                if(!visited[node[i].to]){
                    visited[node[i].to]=true;
                    if(dist[node[i].to]<dist[Q.front()]+val)Q.push_front(node[i].to);
                    else Q.push_back(node[i].to);
                }
            }
        }
    }
}

Swap-SLF优化

很难卡很难卡。。

如果我们的SPFA队列改变了且dist[Q.front()]>dist[Q.back()],那么交换队首队尾。

代码实现：

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
inline void Add_Edge(int from,int to,int color){
    node[++cnt].next=head[from];
    node[cnt].to=to;
    node[cnt].dis=color;
    head[from]=cnt;
}
inline void SPFA(int k){
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++){
        dist[i]=inf;
    }
    deque<int>Q;
    dist[k]=0;
    Q.push_back(k);
    visited[k]=true;
    int first;
    while(!Q.empty()){
        first=Q.front();
        Q.pop_front();
        visited[first]=false;
        for(int i=head[first];i;i=node[i].next){
            if(dist[node[i].to]>dist[first]+node[i].dis){
                dist[node[i].to]=dist[first]+node[i].dis;
                front[node[i].to]=first;
                if(!visited[node[i].to]){
                    visited[node[i].to]=true;
                    if(dist[node[i].to]<dist[Q.front()])Q.push_front(node[i].to);
                    else Q.push_back(node[i].to);
                    if(dist[Q.front()]>dist[Q.back()])swap(dist[Q.front()],dist[Q.back()]);
                }
            }
        }
    }
}

卡SPFA

你们可以看一下某乎上这篇文章。。。

访问链接。

其中有一位用户的回答是这样的：

SPFA的受到怀疑和最终消亡，是OI界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。

作者在此不对这句话做出评论，因为他也没有这样的资格。

但是，sxbk的卡SPFA终究不会让所有OIer满意和赞美。

练习题

T1

luoguP1339

模板题目。

T2

luoguP1529

强制类型转换。

T3

luoguP1828

n遍SPFA。

参考文献

1、洛谷日报第111期2019/1/4。
洛谷日报第111期2019/1/4
2、姬小野的CSDN博客。
姬小野的CSDN博客

THE END