SPFA算法

· · 个人记录

若给定的图有负权边，Dijkstra算法便没有了用武之地，而Bellman-Ford算法时间复杂度又太高，SPFA算法便派上用场了。

SPFA算法在国际上被称为“队列优化的Bellman-Ford算法”，减少了Bellman-Ford算法的冗余运算，仅在中国流行称为“SPFA算法”。

1.算法步骤

  1. 源点入队。
  2. 用队列里的点更新源点到其他点的最短路径，如果更新成功，则判断该点是否还在队列里，如果不在就入队。
  3. 重复 2，直到更新完所有的点。

Code:

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int p,w;
};
int t,n,m;
int dis[2001];
bool vis[2001];//记录点是否在队列中
vector<Edge> e[2001];//vector存图
queue<int> q;
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    q.push(1);
    dis[1]=0;
    while (q.size()){
        int now=q.front();
        q.pop();
        vis[now]=0;//出队，不在队列中
        for (int i=0;i<e[now].size();i++){//更新源点到其他点的最短距离
            int p=e[now][i].p;
            int w=e[now][i].w;
            if (dis[p]>dis[now]+w){
                dis[p]=dis[now]+w;//更新成功
                if (!vis[p]){
                    q.push(p);//该点不在队列里就入队
                    vis[p]=1;
                }
            }
        }
    }
    cout<<dis[n];
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    spfa();
    return 0;
}

2.负环

负环是指一个环中所有边权之和为负的环：

一个含有负环的图无法计算单源最短路。Why？以上图为例，假设我们要求 1 \sim 1 的单源最短路，那么我们可以走一遍负环最后回到 1，这样距离就是 -1。以后我们每走一遍负环最短路径就会增加 -1，我们就可以永无止境的走下去，最短路径也会永无止境的减少。

SPFA算法就可以判负环，若一个点的 入队次数（注意不是松弛次数，如果判断松弛次数在图有重边的时候会出错） 大于 V-1 次则该图一定含有负环。

3.时间复杂度

SPFA算法的时间复杂度是 O(kE)，其中 k 是小常数，在稀疏图中效率较高。但在稠密图或构造网格图中很容易被卡成 O(VE)，此时如果图没有负权边就应该选择更稳定的Dijkstra算法。考场慎用！

4.推荐题目

P3385

P2136

P2850

比较简单的三道题，都是SPFA判负环的板子题。

SPFA：“不！我不想S！！”