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))

    • 核心代码:
    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 的所有出边进行松弛。如果有一条 uv 的边可以使源点到 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)更新分割线↓↓↓


  • 上面提到过,原始的 SPFAbfs的思想,所以每次遇到负边的时候,复杂度就会降为 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 相关优化

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

本文链接:https://snowflake.pink/archives/12/
This blog is under a CC BY-NC-ND 4.0 Unported License