本文最后更新于：2026年10月31日 凌晨
我的 SPFA 怎么又被卡了
0x00. 一切开始之前
上半年帮导师去给学生上 AI 相关的基础课，在讲搜索算法一节的时候刚好讲到了 Dijkstra 算法 ，想了想笔者博客虽然很早就写过 Dijkstra 算法，但是似乎一直没有介绍过更加通用的单源最短路算法 Bellman-Ford Algorithm （ 更多可能是因为 OI 时期 SPFA 经常被出题人数据卡 TLE 不得不用 Dijkstra 所以导致 Dijkstra 以外的最短路算法反而用得不多吧 ），刚好最近也没什么时间写博客，所以简单抽个周末小半天混一篇更新（🕊）
Pre. 图的数据结构表示
开始之前我们重新回顾一下我们用什么样的数据结构表示一张图，一般来说主要有 朴素边表示、邻接表、邻接矩阵 这三种，这里我们重新简单过一遍（ 因为确实很多年没有写过算法相关的博客了，熟悉笔者的读者可能不太熟悉这一块 ）
- 朴素边表示，顾名思义就是直接用一个数组存放图里所有的边
1
2
3
4
5
| #include <tuple>
#include <vector>
typedef std::tuple<int, int, long long> Edge;
typedef std::vector<Edge> Graph;
|
- 邻接表（Adjunct List）可以理解为朴素边表示的一种变体，其将每个节点的边进行单独存放
1
2
3
4
5
| #include <utility>
#include <vector>
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
|
- 邻接矩阵（Adjunct Matrix）则使用矩阵（二维数组）来表示两点间是否存在连通关系，适合稠密图，但是对于稀疏图而言会浪费大量存储空间
1
2
3
| #include <vector>
typedef std::vector<std::vector<long long> > Graph;
|
Pre2. 非负权图上的单源最短路：Dijkstra 算法
重新回顾一下单源最短路问题，Dijkstra 算法应当是最为常见的求 非负权图上的单源最短路 算法了，由非常™著名的荷兰计算机科学家 Dijkstra 在 1956 年提出的，广泛应用于 OSPF 等网络协议与各种涉及图的场景中，并在 FOCS 2024 的一篇名为 Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps 的论文当中被证明具有 普遍最优性 （只能说 Dijkstra 确实🐂🍺嗷）
我们首先简单回顾一下 Dijkstra 的算法过程：
- 首先将所有点的初始距离初始化为 无限大 ，并选取一点为起始点，将其初始距离初始化为 0
- 设置两个集合 S、T，其中 S 为已经选取的点的集合，T 为未选取的点的集合，将所有点加入到集合 T
- 重复如下过程，直到 T 中所有点都被加入 S：
- 在 T 中选取距离最近的点
u ，将其加入到 S
- 遍历
u 所有的边，如果从 u 出发到目标点 v 的距离 dist[u] + w 小于目标点 v 的现有距离 dist[v]，则将 dist[v] 的值更新为 dist[u] + w ，该操作被称之为 松弛 （Relaxation）操作
说实话笔者一直觉得 “松弛” 这个翻译非常糟糕，似乎只不过是把 relaxation 无视语境强行直译罢了
因为 Dijkstra 是先选取点再遍历该点的边，我们不难看出其比较适合使用 邻接表 的方式进行存放，同时我们注意到每次都要遍历一遍所有的未选取点再遍历所有的边，时间复杂度很容易就往 O(N^2) 飙升，因此实践中我们往往会使用 最小二叉堆 （优先队列）优化点的选取过程：
- 选取初始点后，将其距离加入到优先队列中，接下来进行如下循环直到优先队列为空：
- 在优先队列中选取距离最近的点
u （若已被访问则跳过该轮），将其标记为已访问，二叉堆这一数据结构在动态插入删除节点时选取最大最小值有着不错的时间复杂度，因此我们使用该结构替代朴素的最近点选取过程
- 遍历点
u 的所有的边，并进行松弛操作，如果一条边的目标点 v 的距离 dist[v] 被更新，则将点 v 加入到优先队列中，这个 insight 来自于 只有被更新距离的点才对我们有意义 （此时才是可达的），因此我们 只需要遍历所有的可达点
注：算法核心逻辑是没有问题的，但是有的 OI 题目你可能大概率会需要用快读加速，因为很多数据都很神人，例如笔者随便找来测试用的题目 U405825 【模板】堆优化 Dijkstra 而言如果不使用快读则会 TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <climits>
#include <queue>
#include <utility>
#include <vector>
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
struct NodeDist {
int node;
long long dist;
bool operator>(const NodeDist &n) const {
return this->dist > n.dist;
}
};
long long dijkstra(const Graph &g, int node_nr, int start, int end)
{
std::vector<char> visited(node_nr, 0);
std::vector<long long> dist(node_nr, LLONG_MAX);
std::priority_queue<NodeDist, std::vector<NodeDist>, std::greater<NodeDist>> min_heap;
dist[start] = 0;
min_heap.push({start, dist[start]});
while (!min_heap.empty()) {
int u = min_heap.top().node;
long long u_dist = min_heap.top().dist;
min_heap.pop();
if (visited[u] != 0 || u_dist != dist[u]) {
continue;
}
visited[u] = 1;
for (auto i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
long long w = g[u][i].second;
long long new_dist = u_dist + w;
if (dist[v] > new_dist) {
dist[v] = new_dist;
min_heap.push({v, new_dist});
}
}
}
return dist[end];
}
|
Dijkstra 算法 in 负边权图？
虽然 Dijkstra 算法在单源最短路问题上已被证明最优，而且既能用于有向图又能用于无向图，但是存在一个问题便是 无法应用在边权为负的图上 ，因为在有着负边的情况下，一个节点的值可能会需要被多次更新（因为局部贪心会优先走直接近的边，但是多条边拼起来在带有负边的情况下就未必了）， 但在朴素 Dijkstra 算法中，一个已经从 T 集合出来进入 S 集合的点的距离不会再被更新 ，从而导致无法计算出真正的最短路径
如何破局？其实可以想到的一个改进思路是对于一个出队的点，在原本的 Dijkstra 中的设定是其值不会再被更改，那我们就破坏掉这个限制，使其值可以被更改不就好了——虽然听起来似乎能行，但是 这么做的话就已经称不上是 Dijkstra 了 ，毕竟 Dijkstra 的核心是 贪心策略确定一个点的最小距离后就不再更新
——那么这个时候变成了什么算法呢？不如让我们先来看看在带负边权的图上求单源最短路的经典算法：Bellman-Ford 算法
0x01. Bellman-Ford 算法简介
基本思想
Bellman-Ford 算法是由 Richard Bellman 和 Lester Randolph Ford Jr. 分别在 1958 年和 1956 年独立创立的，该算法以 松弛 操作 （relaxation）为核心进行最短路的求解，具体而言：
- 对于有着
n 个点的图，我们不断进行以下循环：
- 尝试对图中 所有的边 进行一次 松弛 操作（即对于权为
w 的边 u->v ，在 dist[v] > dist[u] + w 时，更新 dist[v] = dist[u] + w ，更新 precessor[v] = u）
- 当一轮循环中不存在任何一次成功的松弛操作时，算法终止
——不难看出算法的核心过程 非常简短 ，因为其源于最短路问题上的一个 insight：
- 一条“合法的最短路”（无负环前提下）最多只需要经过 n-1 条边 （所有点连成一条直线）
而 Bellman-Ford 算法在最初始时 只有起始点所连接的边上的点会被松弛，之后不断向外扩散 ，这实际上意味着：
- 每一轮循环，实际上是 最短路信息多向外传播了一条边 ，因此 Bellman-Ford 算法 最多只需要 n - 1 次循环
下面这张来自 Wikipedia 的动图很好地展示了 Bellman-Ford 算法的过程：
此外，这个 insight 帮我们解决了下面的两个问题：
- 一旦图中有带负权值边的环路，无限制的循环是无法停下来的
- 数据未必保证终点是可达的
因此 Bellman-Ford 算法在进行了 n-1 次循环之后，会对这些潜在 exception 进行处理：
- 一旦循环的轮数来到
n-1 时，跳出循环
- 如果
dist[end] 依然未被更新，则说明不可达，直接返回
- 接下来重新进行一轮循环遍历所有的边，一旦仍然能进行松弛操作，则说明图中存在带负权值的边的环路
——整个算法过程非常简单易懂，所以咱们现在直接手搓一个：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <climits>
#include <utility>
#include <vector>
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
bool bellmanford(const Graph &g, std::vector<long long> &dist, int node_nr, int start)
{
bool has_relax;
int loop;
dist.assign(node_nr + 1, LLONG_MAX);
dist[start] = 0;
has_relax = true;
loop = 0;
while (loop < (node_nr - 1) && has_relax) {
has_relax = false;
for (int i = 0; i < node_nr; i++) {
if (dist[i] == LLONG_MAX) {
continue;
}
for (int j = 0; j < g[i].size(); j++) {
int u = i;
int v = g[i][j].first;
long long w = g[i][j].second;
if (dist[v] > (dist[u] + w)) {
dist[v] = dist[u] + w;
has_relax = true;
}
}
}
loop++;
}
if (loop == (node_nr - 1)) {
for (int i = 0; i < node_nr; i++) {
if (dist[i] == LLONG_MAX) {
continue;
}
for (int j = 0; j < g[i].size(); j++) {
int u = i;
int v = g[i][j].first;
long long w = g[i][j].second;
if (dist[v] > (dist[u] + w)) {
return false;
}
}
}
}
return true;
}
|
Bellman-Ford 最多 V 次循环（==节点数），而每个节点最多 E 条边，因此最坏时间复杂度为 O(V * E)
注：这题的数据用 Dijkstra 也能过，因为没有负权边
题目就不摘抄了，简而言之是给了一个带权有向图作为输入，让我们求出从某一点出发到所有点的最短路径长度，可以说是非常经典的单源最短路问题了
直接将我们上面的 Bellman-Ford 算法模板拷贝过来使用即可，唯一要注意的点是对于不可达的点题目要求输出的值是 INT_MAX ：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include <iostream>
#include <climits>
#include <utility>
#include <vector>
using namespace std;
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
bool bellmanford(const Graph &g, std::vector<long long> &dist, int node_nr, int start)
{
bool has_relax;
int loop;
dist.assign(node_nr + 1, INT_MAX);
dist[start] = 0;
has_relax = true;
loop = 0;
while (loop < (node_nr - 1) && has_relax) {
has_relax = false;
for (int i = 1; i <= node_nr; i++) {
if (dist[i] == INT_MAX) {
continue;
}
for (int j = 0; j < g[i].size(); j++) {
int u = i;
int v = g[i][j].first;
long long w = g[i][j].second;
if (dist[v] > (dist[u] + w)) {
dist[v] = dist[u] + w;
has_relax = true;
}
}
}
loop++;
}
if (loop == (node_nr - 1)) {
for (int i = 1; i <= node_nr; i++) {
if (dist[i] == INT_MAX) {
continue;
}
for (int j = 0; j < g[i].size(); j++) {
int u = i;
int v = g[i][j].first;
long long w = g[i][j].second;
if (dist[v] > (dist[u] + w)) {
return false;
}
}
}
}
return true;
}
int main(int argc, char **argv, char **envp)
{
int n, m, s;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> s;
Graph g(n + 1);
vector<long long> dist(n + 1, INT_MAX);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
bellmanford(g, dist, n, s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << ' ';
}
return 0;
}
|
直接 AC：
前面我们已经简要讲解了 Bellman-Ford 算法如何判断负环，现在我们来一道实战的题，题目这里就不摘抄了，简而言之会给 T 组不同的数据，对于存在负环的图我们要输出 YES ，否则输出 NO
因为我们的 Bellman-Ford 模板已经包含了判断负环，所以这里只要直接把前面的模板拷贝过来就行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include <iostream>
#include <climits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
bool bellmanford(const Graph &g, std::vector<long long> &dist, int node_nr, int start)
{
bool has_relax;
int loop;
dist.assign(node_nr + 1, LLONG_MAX);
dist[start] = 0;
has_relax = true;
loop = 0;
while (loop < (node_nr - 1) && has_relax) {
has_relax = false;
for (int i = 1; i <= node_nr; i++) {
if (dist[i] == LLONG_MAX) {
continue;
}
for (int j = 0; j < g[i].size(); j++) {
int u = i;
int v = g[i][j].first;
long long w = g[i][j].second;
if (dist[v] > (dist[u] + w)) {
dist[v] = dist[u] + w;
has_relax = true;
}
}
}
loop++;
}
if (loop == (node_nr - 1)) {
for (int i = 1; i <= node_nr; i++) {
if (dist[i] == LLONG_MAX) {
continue;
}
for (int j = 0; j < g[i].size(); j++) {
int u = i;
int v = g[i][j].first;
long long w = g[i][j].second;
if (dist[v] > (dist[u] + w)) {
return false;
}
}
}
}
return true;
}
void solution(void)
{
int n, m;
std::cin >> n >> m;
std::vector<long long> dist(n + 1);
Graph g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
std::cin >> u >> v >> w;
if (w >= 0) {
g[v].push_back({u, w});
}
g[u].push_back({v, w});
}
if (bellmanford(g, dist, n, 1)) {
std::cout << "NO" << std::endl;
} else {
std::cout << "YES" << std::endl;
}
}
int main(int argc, char **argv, char **envp)
{
int t;
std::cin >> t;
for (int i = 0; i < t; i++) {
solution();
}
return 0;
}
|
直接 AC：
0x02. 优化：Shortest Path Fast Algorithm
朴素 Bellman-Ford 算法虽然简单易懂，但是我们不难发现在朴素 Bellman-Ford 算法当中有着两重循环，内层循环会遍历所有的边（记为 E 条），外层循环最大是点的数量（记为 V 个点，最坏情况下 V-1 次常规循环和 1 次检查循环），因此最终的最坏时间复杂度可以来到 O(V * E) ，从而在某些题目会出现 TLE
如何破局？让我们重新回顾 Bellman-Ford 算法的核心过程：每轮循环遍历所有的边并尝试进行松弛操作，但是实际上我们会发现 仅有那些被松弛了的点对我们才是有意义的，因为只有这些点所连接的边才会引起下一轮松弛 ，对于大部分的边我们实际上做的只是无效的遍历，因此我们不难想到的是 维护一个 FIFO 队列， 当有点被松弛时放入该队列，每次循环从队列中取点并遍历该点的边 ——由此我们就得到了 Bellman-Ford 算法的一种基于队列的变体： Shortest Path Fast Algorithm ，该算法 最初由西安交通大学的段凡丁教授于 1994 年发表于西安交通大学学报
此时我们每次循环的意义从朴素 Bellman-Ford 原本的 “最短路信息向外扩散一条边的长度” 变为 “最短路信息的一次局部传播” ，其正确性来自于：
- 只要某个点的
dist 变小， 它最终一定会被拿出来再处理一次，从而把改进传播出去
——因此当队列为空时，说明没有可以被继续传播的改进了，这等价于 “所有边都满足最短路不等式”
当然，和任何图论问题一样，我们的 SPFA 同样需要考虑终点不可达以及负环的存在性，对于负环的检测，一个比较容易想到的思路就是记录到达某个点所需要使用的边的数量，一旦这个数量超过 n-1 ，则说明存在负环，而对于边的数量的增减则可以通过松弛操作进行判断，因为 u->v 的成功松弛意味着到达 v 所使用的边比到达 u 要多一条，由此将起始点的边数设为 0 之后我们可以在路径扩散过程的松弛操作中同步记录所使用的边的数量
至于不可达的判断就简单了，在没有松弛操作可以进行的情况下如果一个点的距离还没有被更新过，那自然就是不可达了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <climits>
#include <queue>
#include <utility>
#include <vector>
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
bool SPFA(Graph &g, std::vector<long long> &dist, int node_nr, int start)
{
std::queue<int> node_queue;
std::vector<int> edge_cnt(node_nr);
std::vector<char> in_queue(node_nr, 0);
dist.assign(node_nr, LLONG_MAX);
dist[start] = 0;
in_queue[start] = 1;
edge_cnt[start] = 0;
node_queue.push(start);
while (!node_queue.empty()) {
int u = node_queue.front();
node_queue.pop();
in_queue[u] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
long long w = g[u][i].second;
if (dist[v] > (dist[u] + w)) {
edge_cnt[v] = edge_cnt[u] + 1;
if (edge_cnt[v] >= node_nr) {
return false;
}
dist[v] = dist[u] + w;
if (in_queue[v] == 0) {
node_queue.push(v);
in_queue[v] = 1;
}
}
}
}
return true;
}
|
——当然，我们同样要考虑最坏时间复杂度的问题，在最坏的情况下 SPFA 会退化到和朴素 Bellman-Ford 一样的时间复杂度 O(V * E) ，因为 E 条边平摊到 V 个点上，每个点的出度是 E/V ，每个点最坏出队 V 次，所有点就是 V * V * E/V = V * E
和前面一样的例题，不同的是这次我们使用 SPFA 来解决这个问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <iostream>
#include <climits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
bool SPFA(Graph &g, std::vector<long long> &dist, int node_nr, int start)
{
std::queue<int> node_queue;
std::vector<int> edge_cnt(node_nr + 1);
std::vector<char> in_queue(node_nr + 1, 0);
dist.assign(node_nr, INT_MAX);
dist[start] = 0;
in_queue[start] = 1;
edge_cnt[start] = 0;
node_queue.push(start);
while (!node_queue.empty()) {
int u = node_queue.front();
node_queue.pop();
in_queue[u] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
long long w = g[u][i].second;
if (dist[v] > (dist[u] + w)) {
edge_cnt[v] = edge_cnt[u] + 1;
if (edge_cnt[v] >= node_nr) {
return false;
}
dist[v] = dist[u] + w;
if (in_queue[v] == 0) {
node_queue.push(v);
in_queue[v] = 1;
}
}
}
}
return true;
}
int main(int argc, char **argv, char **envp)
{
int n, m, s;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> s;
Graph g(n + 1);
vector<long long> dist(n + 1, INT_MAX);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
SPFA(g, dist, n, s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << ' ';
}
return 0;
}
|
也是直接 AC：
前面我们已经简要讲解了 SPFA 算法如何判断负环，现在我们来一道实战的题，题目这里就不摘抄了，简而言之会给 T 组不同的数据，对于存在负环的图我们要输出 YES ，否则输出 NO
因为我们的 SPFA 模板已经包含了判断负环，所以这里只要直接把前面的模板拷贝过来就行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <iostream>
#include <climits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef std::pair<int, long long> EdgeOut;
typedef std::vector<std::vector<EdgeOut> > Graph;
bool SPFA(Graph &g, std::vector<long long> &dist, int node_nr, int start)
{
std::queue<int> node_queue;
std::vector<int> edge_cnt(node_nr + 1);
std::vector<char> in_queue(node_nr + 1, 0);
dist.assign(node_nr + 1, LLONG_MAX);
dist[start] = 0;
in_queue[start] = 1;
edge_cnt[start] = 0;
node_queue.push(start);
while (!node_queue.empty()) {
int u = node_queue.front();
node_queue.pop();
in_queue[u] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
long long w = g[u][i].second;
if (dist[v] > (dist[u] + w)) {
edge_cnt[v] = edge_cnt[u] + 1;
if (edge_cnt[v] >= node_nr) {
return false;
}
dist[v] = dist[u] + w;
if (in_queue[v] == 0) {
node_queue.push(v);
in_queue[v] = 1;
}
}
}
}
return true;
}
void solution(void)
{
int n, m;
std::cin >> n >> m;
std::vector<long long> dist(n + 1);
Graph g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
std::cin >> u >> v >> w;
if (w >= 0) {
g[v].push_back({u, w});
}
g[u].push_back({v, w});
}
if (SPFA(g, dist, n, 1)) {
std::cout << "NO" << std::endl;
} else {
std::cout << "YES" << std::endl;
}
}
int main(int argc, char **argv, char **envp)
{
int t;
std::cin >> t;
for (int i = 0; i < t; i++) {
solution();
}
return 0;
}
|
直接 AC：
SPFA 的问题
众所周知 OI 界的一个常识是 SPFA 容易被出题人卡，甚至在 NOI 2018 T1 的赛后讲解中，出题人说出了这么一句话——
偷的图，笔者当年比较摸鱼没能进省队，所以也只是听说过这回事 ：(
为什么会有人说 “SPFA死了” ？虽然从“算法复杂度”而言 SPFA 最坏情况也就是和 Bellman-Ford 一样降到 O(VE) ，但是 队列本身的操作也会带来不小开销 ——一个非常简单容易想到的卡 SPFA 的方法就是 加大整个过程在队列上所消耗的时间 ，精心构造的数据非常容易就能够让 SPFA 在队列上产生远超 SPFA 本身的计算时间，从而最后的解题时间反而比朴素 Bellman-Ford 慢不少