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 授权协议，转载请注明来源，谢谢！