SPFA算法深度探究
浏览 460 | 评论 0 | 字数 3258
Snowflake_Pink
2020年03月23日
  • 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))$

      • 核心代码:
      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的模板
    #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$,那么就可以确定这是一个环,所以只要用一个数组来记录一个结点是否在递归栈中就可以了~~
    • 伪代码:
    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相关优化

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

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/12/
    最后修改时间:2020-05-18 18:47:23
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论