AcWing 851. SPFA算法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 851. SPFA算法原题链接简单

作者：

orzorz , 2020-02-29 15:56:42 , 所有人可见 , 阅读 28766

665

479

分析

终于来到SPFA算法了！之前已经说明过了Bellman_ford算法 ,我们今天说明的SPFA算法仅仅只是对该算法的一个优化。
Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。

值得注意的是

1) st数组的作用：判断当前的点是否已经加入到队列当中了；已经加入队列的结点就不需要反复的把该点加入到队列中了，就算此次还是会更新到源点的距离，那只用更新一下数值而不用加入到队列当中。
即便不使用st数组最终也没有什么关系，但是使用的好处在于可以提升效率。
2) SPFA算法看上去和Dijstra算法长得有一些像但是其中的意义还是相差甚远的:

1] Dijkstra算法中的st数组保存的是当前确定了到源点距离最小的点，且一旦确定了最小那么就不可逆了(不可标记为true后改变为false)；SPFA算法中的st数组仅仅只是表示的当前发生过更新的点，且spfa中的st数组可逆(可以在标记为true之后又标记为false)。顺带一提的是BFS中的st数组记录的是当前已经被遍历过的点。
2] Dijkstra算法里使用的是优先队列保存的是当前未确定最小距离的点，目的是快速的取出当前到源点距离最小的点；SPFA算法中使用的是队列(你也可以使用别的数据结构),目的只是记录一下当前发生过更新的点。

3) ⭐️Bellman_ford算法里最后return-1的判断条件写的是dist[n]>0x3f3f3f3f/2;而spfa算法写的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。

4) ⭐️ Bellman_ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；但是SPFA算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用SPFA否则会死循环。

5) ⭐️由于SPFA算法是由Bellman_ford算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 $O(nm)$ ，假如题目时间允许可以直接用SPFA算法去解Dijkstra算法的题目。(好像SPFA有点小小万能的感觉?)

6) ⭐️求负环一般使用SPFA算法，方法是用一个cnt数组记录每个点到源点的边数，一个点被更新一次就+1，一旦有点的边数达到了n那就证明存在了负环。

代码及注释

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=1e5+10;

#define fi first
#define se second

typedef pair<int,int> PII;//到源点的距离，下标号

int h[N],e[N],w[N],ne[N],idx=0;
int dist[N];//各点到源点的距离
bool st[N];
int n,m;
void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int spfa(){
    queue<PII> q;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push({0,1});
    st[1]=true;
    while(q.size()){
        PII p=q.front();
        q.pop();
        int t=p.se;
        st[t]=false;//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率
                    st[j]=true;
                    q.push({dist[j],j});
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int res=spfa();
    if(res==-1) puts("impossible");
    else printf("%d",res);

    return 0;
}

105 评论

shiye 2022-09-06 21:06

作者其他都写得很好，但是第4点需要说明一下，SPFA可以处理负权边，但是不能处理有负权回路的图；而Dijkstra不能处理带有负权边和负权回路的图，因为Dijkstra算法在计算最短路径时，不会因为负边的出现而更新已经计算过(收录过)的顶点的路径长度；
总结一下：Bellman-ford可以处理任意带负权边和负权环的图，SPFA可以处理带负权边的图，Dijkstra只能处理带正权边的图；当然，从时间复杂度的效率来讲，是反过来的，hh

微光_92 2023-03-15 19:46

Bellman-ford处理不了带负权环的图，可能会算出错误答案

忧幽 2023-03-21 10:26 回复了微光_92 的评论

嗯？

doyo 2023-04-18 20:08 回复了微光_92 的评论

存在负权回路的图本身就没有最短路径吧，一直走答案就是负无穷

y差c 2023-09-26 09:36 回复了 doyo 的评论

会限制循环的次数，也就是最多走多少次

TimesSign 12个月前回复了 doyo 的评论

是可能不存在，当负权回路不在目标路径中时便存在

hua_Xia_1125 2022-11-13 14:09

悄悄告诉大家最短路可能为-1，你impossible也是返回-1，所以冲突了

Pobz 2023-01-09 17:56

~~我已经学会了，快删掉~~

人间最失意 2023-03-09 20:58

发现了哈哈

笨死了 2023-04-14 20:53

·上一个Bellman-ford，就在这卡了半天，你小子为啥在SPFA这里说，干嘛啊·

在下令狐冲 2023-10-25 21:44

卡了半天，到你这才明白😂

宇宙分解 2023-04-27 10:30

呜呜呜谢谢宁！！ “ 已经加入队列的结点就不需要反复的把该点加入到队列中了，就算此次还是会更新到源点的距离，那只用更新一下数值而不用加入到队列当中 ” 我还在想这个节点更新了数值那不是他后面连接的节点的数值也要通过这个点跟着更新嘛，但是其实如果这个点已经在队列中，那么等队列中的这个节点到队头，用来更新后面节点时，这个节点的dist已经变为你更新后的值了，加入队列只是加入你的节点编号，通过节点编号永远可以更新、获取节点的dist。即更新了某个节点的dist，如果队列里也有这个节点，队列里的这个节点的dist也就被更新啦！

acwing_00852 9个月前

我自己手动模拟了一下才理解大佬说的什么意思。
点已经在队列中需要再次插入到队列中分为两种情况：
1.点t到邻近点j之间有重边。此时会在邻接表的遍历这一步保存一个最短距离w[i]min;//实际上无论t引出边权的遍历顺序是怎样，都会因为 dist[j]=dist[t]+w[i] 而保留最小的
2.点t->…->点j之间存在若干条不同的路径。由于spfa基于的是bfs的搜索顺序，由点t到点j的bfs层数代表不同路径所经过的点数，那么必定存在一个经过最少节点数（注意：此时不一定是最短路径）的路径，这个路径最先将点j放入队列之中。此后bfs不同的路径，点j距离点i的距离会进行更新，由于dist[j]=dist[t]+w[i]; dis[j]会保留最短的距离。值得一提的是dis[j]被重复更新的次数就等于点t到点j的通路路径个数。

如有错误的地方，请大佬指正

xf. 2023-03-21 22:18

# 改一下结尾就可以AC了

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=1e5+10;

#define fi first
#define se second

typedef pair<int,int> PII;//到源点的距离，下标号

int h[N],e[N],w[N],ne[N],idx=0;
int dist[N];//各点到源点的距离
bool st[N];
int n,m;
void add(int a,int b,int c){
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int spfa(){
    queue<PII> q;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push({0,1});
    st[1]=true;
    while(q.size()){
        PII p=q.front();
        q.pop();
        int t=p.se;
        st[t]=false;//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率
                    st[j]=true;
                    q.push({dist[j],j});
                }
            }
        }
    }

   return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int res=spfa();
    if(res==0x3f3f3f3f) puts("impossible");
    else printf("%d",res);

    return 0;
}

yangyibufeng 2022-07-24 11:51

这个代码现在已经不能ac了，去看y总的代码，但是思路还是正确的

HyPerion- 2023-05-04 22:02

不知道有没有人碰到这个问题

 while(q.size())
    {
        auto t = q.front();
        q.pop();
        int v = t.second;
        **int d = t.first;**        
        st[v]=0;

        for(int i = h[v] ; i!=-1 ; i=ne[i])
        {
            int j = e[i];
            if(dist[j]>d+w[i]) 
            {
                **dist[j]=d+w[i];**
                if(!st[j]){
                    q.push({dist[j],j});
                    st[j]=1;
                }
            }
        }
    }

这样是WA，因为存在没有push但是改变了dist[t]的情况

jxzzzzzz 2023-08-08 21:48

没错hh 这里没必要用pair

命不该绝 2023-03-04 10:18

想问一下为啥用优先队列卡在最后一个数据了？

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10;
priority_queue<PII, vector<PII>, greater<PII>> q;
bool st[N];
int h[N], ne[N * 2], e[N * 2], v[N * 2], d[N];
int n, m, idx = 0;

void add(int a, int b, int x){
    e[idx] = b;
    v[idx] = min(v[idx], x);
    ne[idx] = h[a];
    h[a] = idx++;
}

void spfa(){
    d[1] = 0;
    q.push({0, 1});
    while(q.size()){
        auto t = q.top();
        q.pop();
        int ver = t.second, dis = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis + v[i] < d[j]){
                d[j] = dis + v[i];
                q.push({d[j], j});
            }
        }
    }
}

int main(){
    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);
    memset(v, 0x3f, sizeof v);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, x;
        scanf("%d%d%d", &a, &b, &x);
        add(a, b, x);
    }
    spfa();
    if(d[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << d[n];
    return 0;
}