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))$
- 核心代码：
CPP
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相关优化

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

SPFA算法深度探究

SPFA？？

Bellman−FordBellman-FordBellman−Ford算法

SPFASPFASPFA算法

SPFA的其他优化

基于dfs的SPFA相关优化

$Bellman-Ford$ 算法

$SPFA$ 算法