spfa是bellman-ford的队列优化版本，核心在于仅对距离刚被更新的节点进行松弛，跳过无效边遍历；虽最坏时间复杂度仍为o(ve)，但在稀疏图或负权边较少时实际效率显著提升。
SPFA 就是 Bellman-Ford 的队列优化版本，核心不是“换了个数据结构”，而是**只对距离刚被更新的点做松弛，跳过大量无效判断**。它不保证最坏时间复杂度优于原始 Bellman-Ford（仍是 O(VE)），但在稀疏图、随机图或负权边较少时，实际运行快得多。
为什么普通 Bellman-Ford 效率低？
原始 Bellman-Ford 每轮都遍历所有边，不管起点是否已收敛。比如一个点 u 的 dis[u] 从第 2 轮起就不再变，但后续 5 轮仍会用它去松弛所有出边——纯属冗余。
SPFA 把“哪些点的 dis 刚变过”这个信息显式维护起来，只让它们参与下一轮松弛。
- 用
queue<int></int>存储待处理的顶点编号 - 用
vis[]（或inque[]）标记某点是否已在队列中，避免重复入队 - 每次取队首
u，遍历其所有出边u→v；若能松弛（dis[v] > dis[u] + w），且v不在队列中，则入队 -
u出队后立刻清掉vis[u]标记
SPFA 的关键代码结构怎么写？
别套模板，抓住三个动作：入队、松弛、出队。下面是最简骨架（邻接表 + vector）：
vector<pair int>> graph[MAXN]; // graph[u] = {v, weight}
int dis[MAXN], vis[MAXN];
queue<int> q;
// 初始化
fill(dis, dis + MAXN, INF);
dis[start] = 0;
q.push(start);
vis[start] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0; // 出队即取消标记
for (auto& [v, w] : graph[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) { // 避免重复入队
vis[v] = 1;
q.push(v);
}
}
}
}
</int></pair>
注意：vis[u] = 0 必须在 pop() 后立即执行，否则同一节点可能因多次松弛请求而反复入队——这是常见逻辑错误。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
SPFA 容易踩的坑有哪些？
这些不是“边界情况”，而是上线就崩的硬伤：
-
vis[]数组未初始化为0，导致首次入队失败或误判 - 忘记在
q.pop()后设vis[u] = 0，造成节点永久滞留标记，后续无法再入队 - 用
vector存邻接表时，顶点编号从1开始但数组大小开小了（如graph[MAXN]但MAXN=100，输入n=100时访问graph[100]越界） - 判断松弛条件写成
>=而非>，导致零权自环或重复更新触发死循环 - 没处理负权回路：SPFA 本身不检测，需额外加限制（如记录每个点入队次数 ≥ n 则存在负环）
什么时候该用 SPFA 而不是 Dijkstra？
只有一种情况必须选 SPFA：图含负权边，且你不需要负环检测以外的额外功能。
Dijkstra 在负权边下直接失效（贪心选择失效），而 SPFA 仍能收敛（只要没负环）。但要注意：
- 如果图无负权，Dijkstra（尤其堆优化版）稳定更快，SPFA 可能被卡成 O(VE)
- 如果需要检测负权回路，SPFA 可通过统计
cnt[v]（v 入队次数）实现：一旦cnt[v] >= n，立刻退出并判定存在负环 - 现代 OJ 中，SPFA 常被针对性卡数据，竞赛中更倾向用 Bellman-Ford 的边数限制版或 Johnson 算法替代
真正难的从来不是写对松弛逻辑，而是想清楚：你面对的是稀疏负权图，还是被精心构造的最坏数据——后者会让队列反复膨胀，vis 标记和入队控制稍有松懈，程序就停不下来。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
