文章标题：图论领域中的SPFA算法：便捷高效的路径探寻方法

文章内容：

本篇将带领大家探索SPFA算法；涵盖基础认知、图形分析演示，直至最终的代码实现，还有对代码如此编写缘由的细节阐释，以及相关题型的应用，非常适合刚起步的新手学习；满满都是实用知识，简单易懂；欢迎大家点赞收藏阅读啦！！！

一·本算法背景：

在图论的算法体系里，求解单源最短路径问题是核心且基础的任务，在诸多领域有广泛关键应用。SPFA（Shortest Path Faster Algorithm）作为该领域的经典算法之一，凭借自身独特优势，在处理复杂图结构时扮演重要角色。它不但能处理含负权边的图，还在平均状况下呈现出较高效率，因而在交通规划、通信网络优化、经济决策等多个实际场景中广受青睐。

二·算法核心思想及实例模拟操作：

SPFA算法本质上是对Bellman-Ford算法的一种优化。Bellman-Ford算法通过对图中所有边进行n-1次松弛操作（n为顶点数）来确定最短路径，这种方式虽能保证正确性，但很多时候进行了大量不必要的计算。SPFA算法引入了队列思想，仅对那些距离有可能被更新的顶点进行处理，极大减少了冗余计算。类似BFS但又不完全相同；进入队列的点出去后，仍可能作为最短路径的中间点等再次入队。简言之，入队的点不一定就是最短路径的点；还有可能被更新；并且出队后，可能存在指向它的点u；借助点u到它更近，也就是再次更新该v的dist使其再次入队。虽说SPFA算法相对Bellman-Ford算法更快，但有时因图的特性仍会出现超时等情况，所以使用时也需谨慎考量。

需要的表：
vector> v[N] | in_q数组 | cnt数组| pre数组| 队列| dsit数组
---|---|---|---|---|---
储存u点到达的所有v点及其权值的数组（u为起始，v为终止）| 检查某个点是否存在队列| 记录每个点进入队列的次数| 记录前驱节点|
让可能是最短路径的点入进来| 记录源点距

下面举例子模拟一下：

完成初始化：

具体操作如图：

这样一来其实蛮简单的吧；当然代码也是如此；注意一些细节就好啦！

三.算法详细步骤:

3.1初始化操作：

下面我们根据上面的例子及表格完成对应代码书写：

初始化邻接表：

cin >> n >> m;
for (int i = 0; i < m; i++) {
    int x, y, z;
    //单双向边都可：
    cin >> x >> y >> z;
    v[x].emplace_back(y, z);    
}

初始化pre数组：

void init_pre() {

    for (int i = 1; i <= n; i++)pre[i] = i;
}

初始化dist：

fill(dist + 1, dist + n + 1, maxi);//初始化dist要注意：我们从1-n的点的编号；也就是初始化这个区间（[迭代器)）

其他；这样类似的初始化和我们上一篇的Bellman-Ford算法差不多；可以参考：

【狂热算法篇】探寻图论幽径：Bellman - Ford 算法的浪漫征程（通俗易懂版）-CSDN博客

3.2队列迭代松弛阶段：

也就是说只要队列不存在；然后我们对到达这个p点的边进行松弛成功了；即此时的路径有可能是到达p或者通过p到达其他点的最短路径。因此可能作为最短路径及它的一部分；故入队列；但是还是不太完美；因此就要用到下面的优化了。

dist[s] = 0;
q.push(s);
while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto [p,w] : v[cur]) {

        if (dist[cur] != maxi && dist[cur] + w < dist[p]) {
            dist[p] = dist[cur] + w;
            pre[p] = cur;
            q.push(p);

        }
    }

}

3.3提速小优化：

记录是否在队列中防止重复操作；因为如果队列有相同的点；那么对一个点操作完只可能改变dist p；自身的dist不会变；也就是当再次遍历到下一个同点的时候；不会进行任何操作。

所以只需要在上面代码加上检查数组即可：

dist[s] = 0;
q.push(s);
in_q[s] = 1;
while (!q.empty()) {
    int cur = q.front();
    q.pop();
    in_q[cur] = 0;
    for (auto [p,w] : v[cur]) {

        if (dist[cur] != maxi && dist[cur] + w < dist[p]) {
            dist[p] = dist[cur] + w;
            pre[p] = cur;
            if (!in_q[p]) {// 不在队列中才入队
                q.push(p);
                in_q[p] = 1;

            }
        }
    }

}

3.4检查是否存在负环：

这里我们先放结论；如果一个点被入队列次数超过了n次；那么它一定是存在负环的（正环或0环可以提前找到最短路径；去环无影响；故不可能发生）：

dist[s] = 0;
q.push(s);
in_q[s] = 1;
cnt[s]++;
while (!q.empty()) {
    int cur = q.front();
    q.pop();
    in_q[cur] = 0;
    for (auto [p,w] : v[cur]) {
        if (dist[cur] != maxi && dist[cur] + w < dist[p]) {
            dist[p] = dist[cur] + w;
            pre[p] = cur;
            if (!in_q[p]) {// 不在队列中才入队
                q.push(p);
                in_q[p] = 1;
                cnt[p]++;
                if (cnt[p] > n) return 0;//判断负环

            }
        }
    }

}

四.代码实现：

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
int maxi = 0x3f3f3f3f;
const int N = 1e6 + 1;
int dist[N], n, m;
int pre[N];//前驱节点
vector<pair<int,int>> v[N];//邻接表：储存u及所连接的v和之间的w
queue<int>q;
bool in_q[N] = { 0 };//记录是否在队列中防止重复操作；因为如果队列有相同的点；那么对一个点操作完只可能改变dist p；自身的dist
  //不会变；也就是当再次遍历到下一个同点的时候；不会进行任何操作。
int cnt[N] = { 0 };//记录节点入队列次数；判断是否出现负环
bool SPFA(int s,int n) {//n个点
    fill(dist + 1, dist + n + 1, maxi);//初始化dist要注意：我们从1-n的点的编号；也就是初始化这个区间（[迭代器)）
    dist[s] = 0;
    q.push(s);
    in_q[s] = 1;
    cnt[s]++;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        in_q[cur] = 0;
        for (auto [p,w] : v[cur]) {
           //这里为何会入队列？ 
        //也就是说只要队列不存在；然后我们对到达这个p点的边进行松弛成功了；即此时的路径有可能是到达p或者通过p到达其他点的最短路径
        //因此可能作为最短路径及它的一部分；故入队列。
            if (dist[cur] != maxi && dist[cur] + w < dist[p]) {
                dist[p] = dist[cur] + w;
                pre[p] = cur;
                if (!in_q[p]) {// 不在队列中才入队
                    q.push(p);
                    in_q[p] = 1;
                    cnt[p]++;
                    if (cnt[p] > n) return 0;//判断负环

                }
            }
        }

    }

    return 1;

}

void init_pre() {

    for (int i = 1; i <= n; i++)pre[i] = i;
}
int getpath(int x) {
    pre[x] == x ? x : getpath(pre[x]);
    cout << x << " ";
    return x;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        //单双向边都可：
        cin >> x >> y >> z;
        v[x].emplace_back(y, z);    
    }
    init_pre();

    bool flag=SPFA(1,n);
    if (flag) {
        if (dist[n] == maxi) cout << "unconnected" << endl;
        else {
            cout << dist[n] << endl;
            cout << "最短路径：" << endl;
            getpath(n);
        }
    }
    else {
        cout << "exist negative circle " << endl;
    }
    return 0;

}

五·代码实例测试：

下面我们就来用几组数据测试一下上述的代码：

①看一下到达6号点最短路径是不是1；路途是不是1 2 5 6：

②看一下最终1到4最短路径是不是-3 路途是不是1 3 4：

③测试一下负环：

最终也是成立的；但是有些情况SPFA算法有时候会超时；因此选择的时候还需注意。

六.小细节及疑点剖析：

6.1 为什么可以通过队列进行Bellman-Ford算法的优化操作：

我们上篇讲述了Bellman-Ford算法的原理：对全边n-1次松弛；但是这样就算提前结束也肯定会有的边虽然让它松弛但是也不会更新dist值；也就是重复操作。

那么我们这里就可以用队列：比如某个点u松弛后dist更新了也就是它找到了最短路径或者其他点可以借助这个点u进行找最短路径;因此把它入队列方便找到可以借助它作为中间点的其他点v（可能就是最短路径）。

这里为何会入队列？也就是说只要队列不存在；然后我们对到达这个p点的边进行松弛成功了；即此时的路径有可能是到达p或者通过p到达其他点的最短路径因此可能作为最短路径及它的一部分；故入队列。

总结一下：凡是入队列的点要么已经找到了最短路径要么可能是最短路径要么其他点可以借助入进的这个点的dist找到自己的最短路径。

6.2 cnt记录每个点入队列的次数为什么能实现对负环的判断：

我们SPFA算法同Bellman-Ford算法一样是可以检测出负环的；但是这里SPFA是怎么检测的呢？

我们可以发现当有n条边的时候；源点到达一个点的最短路径除了正环和零环（它们的最短路是绝对不包含环的；因为有环只会延长最短路）一定最长是n-1条边（也就对应着我们Bellman-Ford算法为啥进行n-1次全边松弛操作了。）；那么此时我们可以得出的结论：

n个点的时候；那么源点到达某个点的路径最长就是要经过n-1条边；然后会有最多n条路径；也就是某个点的dist可能最多被更新n次；也就是最多一个点可能会入队列n次；也就是我们的如果存在最小路径的情况下（无环，正环，零环）；因此如果它进入的次数大于n也就说明是负环的情况了。

下面我们就举一下当恰好一个点入队列可能达n次的情况：

6.3为什么in_q要记录某个点是否在队列里：

其实就是防重复操作：

记录是否在队列中防止重复操作；因为如果队列有相同的点；那么对一个点操作完只可能改变dist p；自身的dist不会变；也就是当再次遍历到下一个同点的时候；不会进行任何操作。

下面我们举个例子来说明一下：

七.算法复杂度分析：

7.1时间复杂度：

1. 平均情况 ：在平均情况下，SPFA 算法的时间复杂度为O(km)，其中是一个较小的常数，通常远小于顶点数n，m是边数。这是因为它通过队列优化，只处理那些可能会更新距离的顶点，避免了 Bellman - Ford 算法中对所有边的多次无效松弛操作，大大减少了计算量。
2. 最坏情况 ：然而，在最坏情况下，比如当图存在大量负权边且结构特殊时，SPFA 算法会退化为 Bellman - Ford 算法。此时，它需要对所有边进行n-1次松弛操作（n为顶点数），时间复杂度变为O(nm)。例如，当图是一个链状结构且存在负权边时，SPFA 算法可能会不断地对链上的顶点进行入队和松弛操作，导致时间复杂度急剧上升。

7.2空间复杂度：

1. 存储图的结构 ：算法需要存储图的邻接表来表示图的结构。对于一个有m条边的图，存储邻接表的空间复杂度为O(m)。
2. 辅助数组 ：还需要存储距离数组dist、顶点是否在队列中的数组in_q以及入队次数数组cnt。这些数组的大小都与顶点数n相关，每个数组的空间复杂度为O(n)。因此，总体空间复杂度为O(n+m)。

八·SLF优化及LLL优化策略：

我们不难发现这样普通的SPFA算法每次只能取到队头的元素；这样有可能dist比较小的不是先取到；导致了本来可以提前确定好最短路径；或可能是最短路径的点在后面才会被操作；这样不就相当于麻烦速度变慢了因此我们可以使用deque根据下面两个优化方面进行小小优化：

SLF：即插入时候做优化；LLL：选择元素删除队列时做优化。

8.1SLF（Small Label First）优化：

8.1.1优化原理：

在每次取出队首顶点时，LLL优化策略会检查队首顶点的距离是否大于当前已确定的最短路径长度的平均值。如果大于，则将队首顶点移到队尾，优先处理距离较小的顶点。这样做可以避免长时间处理距离较大的顶点，防止算法在一些距离较大但对最终结果影响较小的顶点上浪费过多时间，从而提高算法的整体效率。

8.1.2实现方式：

在取出队首顶点时增加判断逻辑，根据条件将顶点移到队尾。实现时需要额外记录已确定的最短路径长度之和以及已处理的顶点数，以便计算平均值。

简单来说就是：这里用双端队列进行优化；可以更快的确定某点的最短路径；提前更新出到某点的可能是的最短路径；加快了找到真正的最短路径或者以及找到当前点的最短路径；以及后序的其他点的最短路的速度。

因此我们只需要在源代码特判一下：在入队列的时候和队头元素比较一下；如果dist要小于队头；那么就插队头否则插队尾。

8.1.3 SLF优化代码实现：

```cpp

include

include

include

include

include

using namespace std;
int maxi = 0x3f3f3f3f;
const int N = 1e6 + 1;
int dist[N], n, m;
int pre[N];//前驱节点
vector> v[N];
dequeq;
bool in_q[N] = { 0 };
int cnt[N] = { 0 };//记录节点入队列次数
bool SPFA(int s, int n) {//n个点
fill(dist + 1, dist + n + 1, maxi);//初始化dist要注意：我们从1-n的点的编号；也就是初始化这个区间（[迭代器)）
dist[s] = 0;
q.push_back(s);
in_q[s] = 1;
cnt[s]++;
while (!q.empty()) {
int cur = q.front();
q.pop_front();
in_q[cur] = 0;
for (auto [p, w] : v[cur]) {
if (dist[cur] != maxi && dist[cur] + w < dist[p]) {
dist[p] = dist[cur] + w;
pre[p] = cur;
if (!in_q[p]) {
//这里用双端队列进行优化；可以更快的确定某点的最短路径；提前更新出到某点的可能是的最短路径
//加快