【狂热算法篇】探寻图论幽径之SPFA算法：图论迷宫里的闪电寻径者(通俗易懂版)

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

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

SPFA 算法本质上是对 Bellman - Ford 算法的一种优化。

Bellman - Ford 算法通过对图中所有边进行n-1次松弛操作（n为顶点数）来确定最短路径，这种方式虽然能保证正确性，但在很多情况下进行了大量不必要的计算。

SPFA 算法则引入了队列的思想，它只对那些距离可能被更新的顶点进行处理，从而极大地减少了冗余计算。

类似于BFS但是又不全是；它进过队列的点出去后还可能再次作为最短路径的中间点等再次入。

总之，就是入队不一定就是最短路径的点；还有可能被更新；同时出队后；还有可能有指向它的点u；借助这个点u到它更近；也就是再次更新这个v的dist使得它再次入队。

这里虽然说SPFA算法相对BEllman-Ford算法会快；但是有时候由于图的特点还是会发生超时等操作；所以使用也需要仔细考虑。

首先需要的表：

vector<pair<int,int>> 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 算法的浪漫征程（通俗易懂版）-ZEEKLOG博客

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要记录某个点是否在队列里：

其实就是防重复操作：

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

是不是一下子就恍然大悟了哈哈哈！！！

七.算法复杂度分析：

下面我们从时间和空间两方面来分析一下：

7.1时间复杂度：

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

7.2空间复杂度：

存储图的结构：算法需要存储图的邻接表来表示图的结构。对于一个有m条边的图，存储邻接表的空间复杂度为O(m)。
辅助数组：还需要存储距离数组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优化代码实现：

 #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]; deque<int>q; 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]) { //这里用双端队列进行优化；可以更快的确定某点的最短路径；提前更新出到某点的可能是的最短路径 //加快了找到真正的最短路径或者以及找到当前点的最短路径；以及后序的其他点的最短路的速度 if (!q.empty() && dist[p] < dist[q.front()]) { q.push_front(p); } else { q.push_back(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; }

8.2LLL（Large Label Last）优化：

8.2.1优化原理：

8.2.2实现方式：

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

简单来说就是：在符合front处的节点大于平均值的时候；一直把它移动到back处；直到发现小于了；停止；方便后面取得front的时候是相对小的dsit；同slf优化；尽可能先操作较小的dist的点。

也就是：我们每次选择队头元素时候把它的dsit和全队的dist比较如果小就退出选队头得时候就会选它；否则把它干到队尾；再次比较队头和平均值。

8.2.3LLL优化代码实现：

#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]; deque<int>q; 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]++; int sum_dist = 0; // 队列中所有节点的距离总和 int queue_size = 1; // 队列中节点的数量 while (!q.empty()) { ///LLL优化：在符合front处的节点大于平均值的时候；一直把它移动到back处；直到发现小于了；停止；方便后面取得front的时候是相对小的dsit ///同slf优化；尽可能先操作较小的dist的点 while (!q.empty() && dist[q.front()] * queue_size > sum_dist) { int front_node = q.front(); q.pop_front(); q.push_back(front_node); } int cur = q.front(); q.pop_front(); in_q[cur] = 0; sum_dist -= dist[cur]; queue_size--; 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_back(p); in_q[p] = 1; cnt[p]++; sum_dist += dist[p]; queue_size++; 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; } LLL+SLF的deque优化：

8.3SLF与LLL联合优化：

8.3.1优化原理：

将 SLF 和 LLL 两种优化方法结合使用，可以进一步提高算法在各种图结构下的性能。SLF 策略在入队时优先处理距离小的顶点，而 LLL 策略在出队时避免长时间处理距离大的顶点，两者相互配合，能更有效地减少不必要的计算，加快算法收敛。

8.3.2实现方式：

在代码中同时实现 SLF 和 LLL 的逻辑。在入队时采用 SLF 的入队方式，在出队时采用 LLL 的判断和处理方式，通过合理的逻辑组合，充分发挥两种优化策略的优势。

还是简单说一下：我们的LLL和SLF优化都是让每次选择队头元素的时候操作的尽量是源点距小的点；那么它有可能就是最短源点距；或者其他点可以借助它实现最短源点距的查找从而更快的找到对应的最终的dist值。

归根结底：就是为了提前操作源点距更小的点；让每个点的最终dist值尽快更新完；减少点入队列的次数，提前终止入出队列操作。

8.3.3SLF与LLL联合优化代码实现：

#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]; deque<int>q; 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]++; int sum_dist = 0; // 队列中所有节点的距离总和 int queue_size = 1; // 队列中节点的数量 while (!q.empty()) { ///LLL优化：在符合front处的节点大于平均值的时候；一直把它移动到back处；直到发现小于了；停止；方便后面取得front的时候是相对小的dsit // ///同slf优化；尽可能先操作较小的dist的点 while (!q.empty() && dist[q.front()] * queue_size > sum_dist) { int front_node = q.front(); q.pop_front(); q.push_back(front_node); } int cur = q.front(); q.pop_front(); in_q[cur] = 0; sum_dist -= dist[cur]; queue_size--; 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]) { //这里用双端队列进行优化；可以更快的确定某点的最短路径；提前更新出到某点的可能是的最短路径 // //加快了找到真正的最短路径或者以及找到当前点的最短路径；以及后序的其他点的最短路的速度 if (!q.empty() && dist[p] < dist[q.front()]) { q.push_front(p); } else { q.push_back(p); } in_q[p] = 1; cnt[p]++; sum_dist += dist[p]; queue_size++; 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; }

九.算法优势与局限性:

9.1优势：

可处理负权边：能应对包含负权边的图，像交通网络中运输补贴情况，可准确计算最优路径。
平均复杂度低：借助队列优化，平均时间复杂度为O(km) ，在稀疏图中收敛快。
能检测负权环：通过记录顶点入队次数判断负权环，助于金融套利等场景决策。
实现简单：基于队列和松弛操作，代码结构清晰，适合初学者和快速实现需求。

9.2局限性:

最坏复杂度高：特殊图结构下，时间复杂度退化为 O(nm)，运行时间长。
易被特殊图卡时：如完全图会使算法频繁入队出队，降低性能。
空间开销大：需队列及多个数组，大规模图数据可能内存不足。
不适用于稠密图：稠密图中，队列和松弛操作多，效率不如专门算法。

十·应用场景：

10.1交通网络规划：

①可处理负权边，能应对道路因特殊活动（如促销活动带来运输补贴）导致成本为负的情况，规划出最优运输路径。

②平均复杂度低，在城市交通等稀疏图结构中，能快速算出两点间的最短出行路线。

10.2金融套利分析：

能检测负权环，可发现金融市场中因汇率差异、利率波动等因素形成的套利机会，辅助投资者决策。

10.3社交网络信息传播：

平均复杂度低，适合社交网络这种稀疏图，可计算信息从一个用户到其他用户的最短传播路径，助力精准营销和信息扩散策略制定。

10.4竞赛与学习：

实现简单，便于初学者理解和快速实现，常用于算法竞赛和学习中验证最短路径算法的正确性。

还有其他的用途等等；这里就不一一列举了。

但是还有些由于它的缺点是不能应用的；如：

大规模稠密网络：如集成电路布线问题，SPFA 可能因最坏复杂度高、不适用于稠密图而效率低下，可考虑使用针对稠密图优化的算法，如基于邻接矩阵的 Dijkstra 算法变种。超大规模图数据：在全球互联网拓扑图分析中，因空间开销大可能导致内存不足，可考虑采用分布式算法或内存优化策略。

十一·个人小总结：

本篇我们所介绍的是SPFA算法也就是优化后的Bellman-Ford算法；下面博主总结了一些代码实现技巧及其适用的归纳；还望对大家学习这个算法有帮助。

实现SPFA：通过邻接表u连着多个v以及w（权边）；只要v能借助这个u到达且更新dist（注意u点要是源点可达点）并且v不在队列就入进去；时刻标记是否在队列情况以及某点进过队列的次数cnt。（需要时可维护好pre数组）这也就是普通SPFA实现。

对应SLF和LLL优化：其实一个是插入队列的时候：小于队头元素就插队头大于就插队尾。

另一个就是选择队列中元素的时候，我们每次都要选对头；因此如果发现队头元素的dist小于平均值就放队尾；否则退出循环选择它（这样就实现了每次操作队列中尽可能dist小的点）

四种最短路径算法小总结：

这篇我们的SPFA算法就分享到此；下一篇博主将带大家剖析其他图论算法；欢迎大家订阅呀！！！

一·本算法背景：