精华内容
下载资源
问答
  • Spfa
    2019-09-21 13:08:29

    Spfa

      \(Spfa\) 算法的全称是: \(Shortest\) \(Path\) \(Faster\) \(Algorithm\) ,是 \(Bellman-Ford\) 算法的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。

    基本原理

      设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点 \(u\) ,并且用结点 \(u\) 当前的最短路径估计值对离开结点 \(u\) 所指向的结点 \(v\) 进行松弛操作,即判断是否有 \(dis[v]>dis[u]+w\)\(w\) 是连接 \(u\)\(v\) 的边的长度),若有,则更新 \(dis[v]\) 。如果结点 \(v\) 的最短路径估计值有所调整,且结点 \(v\) 不在当前的队列中,就将结点 \(v\) 放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
      \(Spfa\) 在形式上和 \(Bfs\) 非常类似,不同的是 \(Bfs\) 中一个结点出了队列就不可能重新进入队列,但是 \(Spfa\) 中一个结点可能在出队列之后再次被放入队列,也就是一个结点改进过其它的结点之后,过了一段时间可能本身被改进,于是再次将其加入队列,再次用来改进其它的结点。
      每次将结点放入队尾,都是经过松弛操作达到的。换言之,每次的优化将会有某个结点 \(v\) 的最短路径估计值 \(dis[v]\) 变小。所以算法的执行会使 \(dis\) 越来越小。若图中不存在负权环,则每个结点都有最短路径值。因此,算法不会无限执行下去,随着 \(dis\) 值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。
      如果一个结点进入队列达到 \(n\) 次,则表明图中存在负权环,没有最短路径。

    效率分析

      在随机图中, \(Spfa\) 的期望时间复杂度为 \(O(KE)\) ,其中 \(K\) 是常数,代表所有结点的平均入队次数(一般 \(K≤2\) ), \(E\) 是边数。但往往因为出题人所造的毒瘤数据而被卡,导致复杂度退化为 \(O(VE)\) ,其中 \(V\) 是结点数。

    核心代码

    ll n,m,s,cnt,head[maxn],dis[maxn];
    bool vis[maxn];
    struct Edge{ll u,v,w,next;}edge[maxm];
    void add(ll u,ll v,ll w)                    /*链式前向星存图*/
    {
        edge[++cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].next=head[u];
        head[u]=cnt;
    }
    queue<ll>q;
    void Spfa()
    {
        for(ll i=1;i<=n;i++)dis[i]=INF;         /*初始距离设为INF*/
        dis[s]=0;
        q.push(s);                              /*源点入队*/
        vis[s]=1;
        while(!q.empty())
        {
            ll u=q.front();                     /*队首元素出队*/
            q.pop();
            vis[u]=0;
            for(ll i=head[u];i;i=edge[i].next)  /*寻找与所有以队首 u 为起点的边*/
            {
                ll v=edge[i].v,w=edge[i].w;
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;            /*松弛操作*/
                    if(!vis[v])                 /*若终点 v 不在队列中*/
                    {
                        q.push(v);              /*入队*/
                        vis[v]=1;
                    }
                }
            }
        }
    }

    例题解析

    洛谷 P3371 【模板】单源最短路径(弱化版)

      给出一个有向图 \(G=<V,E>\) ,一个源点 \(S\) ,求点 \(S\) 到图中所有点的最短距离。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define maxn 10005
    #define maxm 500005
    #define INF 2147483647
    template<class T>inline void read(T &x)
    {
        x=0;register char c=getchar();register bool f=0;
        while(!isdigit(c))f^=c=='-',c=getchar();
        while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(f)x=-x;
    }
    template<class T>inline void print(T x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)print(x/10);
        putchar('0'+x%10);
    }
    template<class T>inline void print(T x,char c){print(x),putchar(c);}
    ll n,m,s,cnt,head[maxn],dis[maxn];
    bool vis[maxn];
    struct Edge{ll u,v,w,next;}edge[maxm];
    void add(ll u,ll v,ll w)
    {
        edge[++cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].next=head[u];
        head[u]=cnt;
    }
    queue<ll>q;
    void Spfa()
    {
        for(ll i=1;i<=n;i++)dis[i]=INF;
        dis[s]=0;
        q.push(s);
        vis[s]=1;
        while(!q.empty())
        {
            ll u=q.front();
            q.pop();
            vis[u]=0;
            for(ll i=head[u];i;i=edge[i].next)
            {
                ll v=edge[i].v,w=edge[i].w;
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    if(!vis[v])
                    {
                        q.push(v);
                        vis[v]=1;
                    }
                }
            }
        }
    }
    int main()
    {
        read(n),read(m),read(s);
        ll u,v,w;
        for(ll i=1;i<=m;i++)
        {
            read(u),read(v),read(w);
            add(u,v,w);
        }
        Spfa();
        for(ll i=1;i<=n;i++)print(dis[i],' ');
        return 0;
    }

    转载于:https://www.cnblogs.com/LengYun/p/11460428.html

    更多相关内容
  • SPFA.cpp SPFA算法

    2020-10-13 15:50:55
    最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
  • SPFA算法 此处为SPFA算法详解 用dis数组记录源点到有向图上任意一点距离,其中源点到自身距离为0,到其他点距离为 INF。将源点入队,并重复以下步骤: 1、队首x出队 2、遍历所有以队首为起点的有向边(x,i),若...
  • spfa.cpp 算法spfa的板子

    2020-04-23 14:45:31
    自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
  • spfa算法的java实现

    2021-04-17 10:30:56
    spfa算法的java实现
  • SPFA 算法实例讲解

    2020-08-29 23:58:06
    下面小编就为大家带来一篇SPFA 算法实例讲解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • spfa

    多人点赞 2021-05-02 10:23:14
    文章目录前言一、什么是spfa算法二、例题,代码1.AcWing 851. spfa求最短路本题分析AC代码2.AcWing 852. spfa判断负环本题分析AC代码三、时间复杂度 前言 复习acwing算法基础课的内容,本篇为讲解基础算法:spfa,...


    前言

    复习acwing算法基础课的内容,本篇为讲解基础算法:spfa,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


    一、什么是spfa算法

    计算最短路算法的一种,spfa算法可以说是bellman-ford算法的算法优化版本,相较于Dijkstra算法,它可以计算有负权边的最短路,下图来自ACWing算法基础课,关于Dijkstra算法的详细讲解,见博客:Dijkstra,关于bellman-ford算法见博客:bellman-ford
    在这里插入图片描述


    二、例题,代码

    1.AcWing 851. spfa求最短路

    本题链接:AcWing 851. spfa求最短路
    本博客提供本题截图:

    在这里插入图片描述

    本题分析

    我们的spfa算法是在bellman-ford算法的基础上进行了优化,所以在这里只讲解优化部分,具体的其他部分的含义,详细见博客:bellman-ford
    在bellman-ford算法中我们会遍历所有的边,但是很多的边的遍历是没有意义的,通过对bellman-ford算法的算法核心进行观察我们会发现:

        for (int i = 0; i < k; i ++ )
        {
            memcpy(backup, dist, sizeof dist);
            for (int j = 0; j < m; j ++ )
            {
                auto t = eg[j];
                dist[t.b] = min(dist[t.b], backup[t.a] + t.w);
            }
        }
    

    对dist数组的更新中,dist[t.b]的更新是因为dist[t.a]的更新,故根据这一点,我们没必要遍历所有的边,只有当这个点更新后,后续的点才会更新,考虑到这里,我们创建一个队列(STL),把我们每一次更新的点加入到队列中.关于队列的详细讲解见博客:STL—queue,关于手写队列,见博客:用数组模拟队列

    AC代码

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int h[N], w[N], e[N], ne[N], idx;
    int dist[N];
    bool st[N];
    
    void add(int a, int b, int c)
    {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    int spfa()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        queue<int> q;
        q.push(1);
        st[1] = true;
    
        while (q.size())
        {
            int t = q.front();
            q.pop();
    
            st[t] = 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])
                    {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    
        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 t = spfa();
    
        if (t == 0x3f3f3f3f) puts("impossible");
        else printf("%d\n", t);
    
        return 0;
    }
    

    2.AcWing 852. spfa判断负环

    本题链接:AcWing 852. spfa判断负环
    本博客给出本题截图

    在这里插入图片描述

    本题分析

    本题中我们用cnt数组去记录边数,cnt[i]表示的是从第一个点到第i个点有多少条边,我们知道,n个点的话最多有n - 1条边,如果某一个点的cnt ≥ n的话,那么就可以证明一定存在负权回路,和第一道例题不同的是,我们不能只把第一个点加入到我们的queue中,因为可能第一个点的路径中没有负权回路,别的点的路径中有,所以我们需要把所有的点都加入到queue中.

    AC代码

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int N = 2010, M = 10010;
    
    int n, m;
    int h[N], w[M], e[M], ne[M], idx;
    int dist[N], cnt[N];
    bool st[N];
    
    void add(int a, int b, int c)
    {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    bool spfa()
    {
        queue<int> q;
    
        for (int i = 1; i <= n; i ++ )
        {
            st[i] = true;
            q.push(i);
        }
    
        while (q.size())
        {
            int t = q.front();
            q.pop();
    
            st[t] = 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];
                    cnt[j] = cnt[t] + 1;
    
                    if (cnt[j] >= n) return true;
                    if (!st[j])
                    {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    
        return false;
    }
    
    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);
        }
    
        if (spfa()) puts("Yes");
        else puts("No");
    
        return 0;
    }
    

    三、时间复杂度

    关于spfa算法的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

    展开全文
  • SPFA

    2019-09-29 07:37:44
    SPFA算法的实现:  BFS版SPFA基本算法实现:  利用一个队列来保存待优化的结点,优化时每次取出队首结点u,并用u点当前的最短路估计值对u点所指向的结点v进行松弛操作,如果结点v不在当前队列中,就将v点放入...

    SPFA算法的实现:

      BFS版SPFA基本算法实现:

      利用一个队列来保存待优化的结点,优化时每次取出队首结点u,并用u点当前的最短路估计值对u点所指向的结点v进行松弛操作,如果结点v不在当前队列中,就将v点放入队尾。这样不断从队首取出结点进行松弛操作,直到队列为空,这样所有的松弛操作都已经结束,对最短路的求解也结束了,因为已经没有结点可以更新距离了,自然求完最短路了。

     

    SPFA算法应用:

     

      求解单源最短路/最长路。

     

       BFS版SPFA求负环:

       如果某一个结点的入队次数超过n次,则存在负环。因为如果图中存在负环,那么一个结点肯定会重复入队超过n次的。

      

    void Spfa(int s)
    {
        flag=false;
        for(int i=0;i<maxn;i++)
            dis[i]=2e18;
        memset(vis,0,sizeof(vis));
        dis[s]=0,cont[s]=1;
        queue<int>q;
        q.push(s);
        while(q.size())
        {
            int u=q.front();q.pop();
            for(int i=head[u];i;i=p[i].nxt)
            {
                int v=p[i].to;
                if(dis[v]>dis[u]+p[i].val)
                {
                    dis[v]=dis[u]+p[i].val;
                    cont[v]++;
                    if(cont[v]>=n)
                    {
                        flag=true;
                        break;
                    }
                    q.push(v);
                }
            }
        }
    }

     

      #10086. 「一本通 3.3 练习 3」Easy SSSP:https://loj.ac/problem/10086

      解题思路:模板题,直接用SPFA判负环并求解最短路,但是因为题目中要判断图中是否存在负权回路,并不一定要将源点S包括在负环中,所以每个点都跑一次BFS版的SPFA,最后再从源点跑一次求最短距离。

      

    #include<bits/stdc++.h>
    using namespace std;
    #define re register int
    #define ll long long
    #define INF 0x7ffffff
    #define maxn 1009
    #define maxm 100009 
    inline ll read()
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
        return x*f;
    }
    bool vis[maxn];
    bool flag;
    int head[maxn],cont[maxn];
    ll dis[maxn];
    struct edge
    {
        int to,nxt;
        ll val;
    }p[maxm];
    int n,m,k,ans,tot,cnt,s; 
    
    void add(int  x,int y,ll z)
    {
        ++cnt,p[cnt].to=y,p[cnt].nxt=head[x],head[x]=cnt,p[cnt].val=z;
    }
    void Spfa(int s)
    {
        flag=false;
        for(int i=0;i<maxn;i++)
            dis[i]=2e18;
        memset(vis,0,sizeof(vis));
        dis[s]=0,cont[s]=1;
        queue<int>q;
        q.push(s);
        while(q.size())
        {
            int u=q.front();q.pop();
            for(int i=head[u];i;i=p[i].nxt)
            {
                int v=p[i].to;
                if(dis[v]>dis[u]+p[i].val)
                {
                    dis[v]=dis[u]+p[i].val;
                    cont[v]++;
                    if(cont[v]>=n)
                    {
                        flag=true;
                        break;
                    }
                    q.push(v);
                }
            }
        }
    }
    int main()
    {
    //    freopen(".in","r",stdin);
    //    freopen(".out","w",stdout);
        n=read(),m=read(),s=read();
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read();
            ll z=read();
            add(x,y,z);
            if(x==y&&z<0)
                flag=true;
        }
        for(int i=1;i<=n;i++)
            if(!cont[i])
                Spfa(i);
        if(flag)
        {
            printf("-1");
            return 0;
        }
        Spfa(s);
        for(int i=1;i<=n;i++)
        {
            if(dis[i]==2e18)
                puts("NoPath");
            else
                printf(i==n?"%lld":"%lld\n",dis[i]);
        }
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    View Code

     

     

     

      DFS版SPFA求负环:

      在BFS版的SPFA中用一个循环的队列来保存需要继续迭代的结点,每一次扩展出一个新的节点必然放到队列的队尾,这样就中断了迭代的连续性,不可以一直迭代下去。但是如果如果采用dfs的思想,每次便可以直接从新结点继续往下扩展。

      DFS对于负环的判断条件更为简单,因为假如存在负环,那么肯定会由一个点出发,最后又回到了这个店,所以只需要判断是否已经在栈中,也就是是否被访问过,但是由于图可能本来就是多个联通快,即不连通,所以每个点都要做一次。

      

      #10084. 「一本通 3.3 练习 1」最小圈:https://loj.ac/problem/10084

      解题思路:https://www.cnblogs.com/Dxy0310/p/9782205.html

     

    转载于:https://www.cnblogs.com/Dxy0310/p/9781742.html

    展开全文
  • c++ SPFA算法

    2019-03-05 20:12:37
    SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
  • cpp代码-SPFA模板

    2021-07-14 17:33:24
    cpp代码-SPFA模板
  • 摘要:VC/C++源码,算法相关,队列优化,最短路径算法 C++队列优化的Bellmanford最短路算法(SPFA),使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一...
  • SPFA算法.ppt

    2015-08-04 15:15:33
    基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束; 利用了每个点不会更新次数太多的...
  • 算法合集之《SPFA算法的优化及应用》.pdf
  • dijkstra和spfa

    2017-11-14 14:55:16
    dijkstra和spfa用c++的实现,实现了求单源最短路径的算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,335
精华内容 23,734
关键字:

SPFA