SPFA
SPFA 简介
SPFA，全称一般写作 Shortest Path Faster Algorithm。
它可以看作是 Bellman-Ford 的队列优化版，用来求解 单源最短路，并且：
- 可以处理负边
- 可以判负环
- 在很多普通数据下跑得比 Bellman-Ford 快
- 但 最坏复杂度仍然很差
在 OI 圈里，SPFA 是一个“很经典，但也很危险”的算法：
- 能写
- 要会判负环
- 但不能无脑拿来跑最短路
一、SPFA 是怎么来的
Bellman-Ford 每一轮都要扫一遍所有边，总共扫 n-1 轮，所以复杂度是：
[ O(nm) ]
但实际上，并不是每条边每次都会产生贡献。
只有那些 刚被更新过的点，它们的出边才有可能继续松弛别人。
于是就有了 SPFA 的想法：
- 如果某个点
u的最短路刚刚变小 - 那么把
u放进队列 - 只去检查
u的出边 - 若更新了相邻点
v，再把v入队
也就是说：
只处理“可能继续产生贡献”的点。
这就是 SPFA 的核心优化。
二、核心思想
设 dist[s] = 0，其余点设为正无穷。
维护一个队列，初始把源点 s 放进去。
每次取出队首点 u，扫描它的所有出边 u -> v (w)：
如果
[ dist[v] > dist[u] + w ]
那么更新 dist[v]。
如果 v 当前不在队列中，就把 v 加入队列。
这样不断进行，直到队列为空，说明当前已经没有点能继续松弛别人了。
三、为什么它是对的
本质上，SPFA 仍然在做 Bellman-Ford 的“松弛”。
区别仅仅在于：
- Bellman-Ford：机械地反复扫描所有边
- SPFA：只扫描那些“刚被更新”的点的出边
所以 SPFA 并没有改变最短路的正确性基础，它只是减少了很多无效松弛。
四、时间复杂度
这是 SPFA 最需要注意的地方。
理论最坏复杂度
[ O(nm) ]
也就是说，最坏情况下和 Bellman-Ford 一个级别。
而且在一些专门构造的数据下，它会非常慢，甚至被卡爆。
实际表现
在很多随机图、普通图、部分实际题目中，SPFA 常常比较快。
所以它是一个“平均看着不错，但最坏不稳”的算法。
五、适用场景
SPFA 常见用途：
- 单源最短路，图中有负边
- 判负环
- 某些差分约束建图题
- 图规模不太极端，或者题目数据对 SPFA 友好
但要记住：
- 没有负边时，一般优先用 Dijkstra
- 只为了最短路而不是负环，SPFA 往往不是第一选择
- 被卡常/卡复杂度的题，SPFA 可能寄
六、标准 OI 模板
1. 单源最短路模板
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long INF = 1e18;
struct Edge {
int to;
long long w;
};
vector<Edge> g[N];
long long dist[N];
bool inq[N];
void spfa(int s, int n) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
inq[i] = false;
}
queue<int> q;
dist[s] = 0;
q.push(s);
inq[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (auto e : g[u]) {
int v = e.to;
long long w = e.w;
if (dist[u] != INF && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!inq[v]) {
q.push(v);
inq[v] = true;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
spfa(s, n);
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) cout << "INF ";
else cout << dist[i] << " ";
}
cout << '\n';
return 0;
}
七、模板解释
1. inq[] 是干什么的
bool inq[N];
表示某个点当前是否在队列中。
作用是避免一个点被重复入队很多次。
如果没有这个数组，某些点可能连续被塞进队列，常数会很难看。
2. 为什么出队时要 inq[u] = false
int u = q.front(); q.pop();
inq[u] = false;
因为这个点已经不在队列里了。
这样之后若它再次被更新，还能重新入队。
3. 为什么不用 vis[]
Dijkstra 里常见“确定最短路后不再变化”的贪心性质。
但 SPFA / Bellman-Ford 没有这个性质，所以不能写：
- “某点处理过一次就永远不管了”
它可能被后续负边继续更新。
八、负环判定
这是 SPFA 很重要的用途。
判定原理
如果一个点的最短路被更新了太多次，就说明可能经过了负环。
更准确地说：
- 若从源点出发，某个点被松弛次数达到
n - 说明存在一条至少含
n条边的更优路径 - 根据抽屉原理，这条路径中必然有环
- 还能继续变优，因此这个环是负环
判负环模板（从源点可达）
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long INF = 1e18;
struct Edge {
int to;
long long w;
};
vector<Edge> g[N];
long long dist[N];
bool inq[N];
int cnt[N]; // 记录每个点被松弛的次数
bool spfa(int s, int n) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
inq[i] = false;
cnt[i] = 0;
}
queue<int> q;
dist[s] = 0;
q.push(s);
inq[s] = true;
cnt[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (auto e : g[u]) {
int v = e.to;
long long w = e.w;
if (dist[u] != INF && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return false; // 存在负环
if (!inq[v]) {
q.push(v);
inq[v] = true;
}
}
}
}
return true; // 无负环
}
不过上面这种写法里 cnt[v] = cnt[u] + 1 更像“路径边数估计法”，竞赛中更常见的写法其实是“入队次数”统计：
更常用的负环判定模板
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long INF = 1e18;
struct Edge {
int to;
long long w;
};
vector<Edge> g[N];
long long dist[N];
bool inq[N];
int cnt[N]; // 记录每个点入队次数
bool spfa(int s, int n) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
inq[i] = false;
cnt[i] = 0;
}
queue<int> q;
dist[s] = 0;
q.push(s);
inq[s] = true;
cnt[s]++;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (auto e : g[u]) {
int v = e.to;
long long w = e.w;
if (dist[u] != INF && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!inq[v]) {
q.push(v);
inq[v] = true;
cnt[v]++;
if (cnt[v] >= n) return false; // 有负环
}
}
}
}
return true;
}
这个版本在题目里最常见。
九、如果要判“图中任意负环”
上面模板判的是：
从源点 s 可达的负环
如果题目要求判整张图是否存在任意负环，常用做法有两个。
做法一：超级源点
建一个新点 0，向所有点连一条权值 0 的边，然后从 0 跑 SPFA。
这样整张图所有点都可达，就能检测整图负环。
做法二：所有点初始入队
更常见的写法是：
- 把所有点都放进队列
dist[i] = 0- 直接开始跑
模板如下：
bool detect_negative_cycle(int n) {
queue<int> q;
for (int i = 1; i <= n; i++) {
dist[i] = 0;
inq[i] = true;
cnt[i] = 1;
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (auto e : g[u]) {
int v = e.to;
long long w = e.w;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!inq[v]) {
q.push(v);
inq[v] = true;
cnt[v]++;
if (cnt[v] >= n) return true;
}
}
}
}
return false;
}
十、SPFA 和 Bellman-Ford 的关系
可以把它们理解成：
- Bellman-Ford：暴力扫所有边
- SPFA：只扫“最近被更新的点”的出边
所以 SPFA 是 Bellman-Ford 的优化实现，而不是另一个完全不同的理论体系。
十一、SPFA 和 Dijkstra 的对比
Dijkstra
- 只能处理 非负边
- 复杂度优秀
- 最短路首选
SPFA
- 可以处理 负边
- 能判 负环
- 最坏复杂度不稳
所以竞赛里通常是：
- 无负边：Dijkstra
- 有负边/判负环：Bellman-Ford 或 SPFA
- 卡 SPFA：要小心题目是否故意针对它
十二、常见优化
SPFA 有两个很经典的启发式优化。
1. SLF（Small Label First）
如果新入队点的 dist 比队首还小，就插到队首。
这样更小的点优先处理，有时会快很多。
一般用 deque 实现。
模板
void spfa(int s, int n) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
inq[i] = false;
}
deque<int> q;
dist[s] = 0;
q.push_back(s);
inq[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop_front();
inq[u] = false;
for (auto e : g[u]) {
int v = e.to;
long long w = e.w;
if (dist[u] != INF && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!inq[v]) {
if (!q.empty() && dist[v] < dist[q.front()]) q.push_front(v);
else q.push_back(v);
inq[v] = true;
}
}
}
}
}
2. LLL（Large Label Last）
如果队首点的距离过大，就把它扔到队尾。
这个优化也比较经典，但实现和收益常常不如 SLF 直观。
OI 里最常见的是：
- 普通队列版
deque + SLF版
十三、典型应用：差分约束
SPFA 在差分约束里非常常见。
例如约束：
[ x_v - x_u \le w ]
可以转化为一条边：
[ u \to v,\ w ]
然后：
- 求可行解
- 判是否无解（有负环）
这类题里 SPFA 经常出现，因为：
- 图里可能有负边
- 需要判负环
- 不一定是单纯的最短路问题
十四、竞赛里常见坑
1. 别把 SPFA 当万能最短路
很多新手会觉得：
“SPFA 能负边，也能正边，那我以后全用它。”
这是不对的。
因为在无负边图上，Dijkstra 通常更稳、更快，也更不容易被卡。
2. 最坏复杂度真的可能炸
不是说“理论最坏”，而是 真的有人专门卡 SPFA。
尤其在一些老题、模板题、出题人熟悉数据构造的题里，SPFA 很危险。
3. 判负环时计数别写错
最常见两种计数：
- 记录入队次数
cnt[v] - 记录路径边数估计
一般推荐用 入队次数，更稳、更常见。
4. INF 要够大
const long long INF = 1e18;
图上边权可能很大，距离也可能累加很大，别用太小的无穷。
5. 判整图负环和判源点可达负环不是一回事
- 从源点出发跑：只能判源点可达部分
- 整图判负环：要超级源点或所有点初始化入队
这个在题目里非常容易看漏。
十五、一句话理解 SPFA
SPFA 的本质就是：
把 Bellman-Ford 中“无脑扫描所有边”改成“只从最近被更新的点继续扩展”，从而减少很多无效松弛。
十六、总结
SPFA 的关键词可以概括为：
- 单源最短路
- 可处理负边
- 可判负环
- Bellman-Ford 队列优化
- 最坏复杂度不稳
你可以把它记成下面这张口袋版：
什么时候用
- 有负边
- 需要判负环
- 差分约束
什么时候别乱用
- 普通非负边最短路
- 题目可能卡复杂度
- 大图高强度数据
最常用模板
- 普通队列 SPFA
- 判负环版 SPFA
deque + SLF优化版