SPFA算法

前言

SPFA算法是Bellman_ford算法的优化，所以我们先了解一下Bellman_ford算法。

Bellman_ford算法

Bellman-Ford算法是一种用于求解单源最短路径问题的经典算法，其目标是找出从单个源点出发到图中所有其他顶点的最短路径。该算法适用于带有负权边的图。

思想

Bellman-Ford算法采用一种松弛（relaxation）的策略来逐步逼近最短路径。其基本思想可以概括为以下几个步骤：

初始化：将源点到所有其他顶点的距离设置为无穷大，源点自身的距离设置为0。

松弛操作：对图中的每一条边进行松弛操作，即尝试通过当前路径缩短已知的最短路径。如果通过该边可以获得更短的路径，则更新相应顶点的最短路径值。

迭代：重复进行松弛操作，一共进行V-1次（其中V为图中顶点的数量），以确保所有可能的最短路径都被考虑到。

检测负权回路：如果在V-1次迭代后还存在可以松弛的边，说明图中存在负权回路，因此无法得到准确的最短路径。算法将停止并报告负权回路的存在。不过我们一般不用bellman_ford算法求负环，而是用SPFA

松弛操作: 用一条边尝试去更新最短路径就叫松弛操作

注意:在每次迭代的时候，需要把当前dis数组备份一下，防止更新的时候出现串联。

▶

代码

//求解从 1 到 n 号节点的、最多经过 k 条边的最短距离。
const int N = 510,M = 10010;
int dis[N],backup[N];
vector<tuple<int,int,int> > eg;
void bellman_ford(int s = 1)
{
    int u,v,w;
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    for(int i=0;i<k;++i)
    {
        memcpy(backup,dis,sizeof dis);
        for(int j=0;j<m; ++ j)
        {
            tie(u,v,w) = eg[j];
            dis[v] = min(dis[v],backup[u] + w);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for(int i=0,a,b,w;i<m;++i)
    {
        cin >> a >> b >> w;
        eg.emplace_back(a,b,w);
    }
    bellman_ford();
    if(dis[n] > INF / 2) puts("impossible");//因为有边数的限制，所以没遍历到的情况大概率不是INF,而是小于INF
    else cout << dis[n] << endl;
    return 0;
}

适用性

Bellman-Ford算法适用于一般的加权图，包括存在负权边的情况。但是，由于它的时间复杂度相对较高$O(nm)$，当处理没有负权边的图时，通常更倾向于使用Dijkstra算法。

SPFA算法

这个算法是一个很神奇的算法，时间复杂度是$O(km)$,k是一个常数，基本上是一个线性的算法，但是一些特殊的数据可以把SPFA算法的时间复杂度卡到$O(nm)$。尽管可以对SPFA再做一些优化，可惜这些优化也还是有对应的数据会给你卡掉。

SPFA（Shortest Path Faster Algorithm）算法是Bellman-Ford算法的一种优化版本，通过队列的方式避免了不必要的松弛操作，从而提高了算法的效率。SPFA算法在实际应用中相对于普通的Bellman-Ford算法具有更快的收敛速度。

每次松弛过程，我们保留那些dis值更新过的点，而在下一次松弛的时候，仅仅需要把这些点当起始节点进行松弛即可，所以剩下了很多不必要的松弛操作。

过程

初始化：将源点的最短路径估计值设置为0，其他顶点的最短路径估计值设置为无穷大。将源点入队。

队列操作：从队列中取出一个顶点，对该顶点的所有邻接边进行松弛操作。如果通过该边可以获得更短的路径，则更新相邻顶点的最短路径估计值。

入队条件：如果某个顶点的最短路径估计值发生改变，并且该顶点不在队列中，则将它入队。这是SPFA算法的关键之一，通过队列来避免不必要的重复松弛操作。

重复操作：重复进行队列操作，直到队列为空。

判正负环

SPFA判负环的思路是：当路径经过节点超过n(点数)时，图存在负环。

当我们一直绕着负环走时，由负环定义，该环边权和为负数，我们走的路径权值和是越来小的。所以当图存在负环时，最短路无解(-INF)。若一张图连通，那么它肯定是可以在经过<=n个节点从一点到任意一点的。不存在负环时，一条路径最多经过n个节点，；存在负环时，spfa就会一直绕着负环走，经过的节点一定超过n，所以只用判断最短路经过节点点数即可。

所以拿一个cnt数组来维护即可。

模板

vector<int> dis(n + 1, 0x3f3f3f3f);
auto spfa = [&](int s = 1) -> bool {
    int y, w;
    using PII = pair<int, int>;
    vector<int> st(n + 1), cnt(n + 1);
    queue<int> q;
    q.emplace(s);//
    dis[s] = 0;//
    st[s] = 1;//
    // for(int i=1;i<=n;++i) q.emplace(i),st[i] = 1;//判断负环，一般要全部点加入
    while (q.size()) {
        auto x = q.front();
        q.pop();
        st[x] = 0;
        for (auto el : h[x]) {
            // tie(y,w) = el; // tie开销更大可能会超时
            y = el.first, w = el.second;
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                cnt[y] = cnt[x] + 1;//判断负环
                if (cnt[y] >= n)
                    return true;
                if (!st[y])
                    q.emplace(y), st[y] = 1;
            }
        }
    }
    return false;
};

那如何判正环呢，很简单，最短路换成最长路就行了。