C++怎么实现SPFA算法_C++单源最短路教程【优化】

林译川

2026-09-20 • 👁 0人浏览过

SPFA 不超时的关键是严格控制入队逻辑和松弛条件：仅当距离更新成功时才入队，用 std::queue 和 in_queue[] 数组避免重复松弛，链式前向星存图，并初始化 dist[] 为极大值。 SPFA 在 C++ 里怎么写才不超时 SPFA 本质是 Bellman-Ford 的队列优化，但很多人直接套模板却在稀疏图上被卡成

O(VE)

，甚至比朴素 Dijkstra 还慢。关键不是“会不会写”，而是“怎么控制入队逻辑”和“怎么避免重复松弛”。用

std::queue

而非

std::priority_queue

—— SPFA 不依赖堆序，堆反而破坏其松弛顺序优势必须维护

in_queue[]

数组，只让节点首次入队或距离更新后再次入队，禁止无脑

push

对每个出队节点

u

，遍历其邻接边时，仅当

dist[v] > dist[u] + w

成立才更新，并检查

v

是否已在队列中慎用

vector>>

存图：小图没问题，但边数 > 1e5 时，连续内存访问不如链式前向星（

head[]

to[]

w[]

nxt[]

）快为什么 SPFA 会被卡、什么情况下该换 Dijkstra SPFA 最坏复杂度仍是

O(VE)

，而恶意构造的网格图、菊花图、负权环附近节点反复入队，很容易触发。它只在“存在负权边且图稀疏、负权分布分散”时有实际优势。若图中无负权边，直接用

priority_queue

dijkstra()

，稳定

O(E log V)

若只有少量负权边（比如 ≤ 3 条），可考虑

0-1 BFS

或分层图建模，而非硬上 SPFA 判负环时，需统计每个节点入队次数：一旦

cnt[v] >= V

，立刻返回负环；但注意——

cnt[]

必须在每次

dist[v]

更新成功后才自增，不能放在入队前

std::queue

和手写循环队列有区别吗对大多数 OJ 数据，

std::queue

（基于

deque

）完全够用；但如果你在本地跑大规模随机图或嵌入式环境受限，手写数组模拟的循环队列能省掉动态内存分配开销。 C知道 CSDN推出的一款AI技术问答工具下载手写要点：设数组大小为

MAXN

，用

head

和

tail

下标，

(tail + 1) % MAXN != head

判满别用

vector::push_back()

模拟队列——每次扩容可能触发 memcpy，实测比

std::queue

慢 20%~40%

std::queue

默认底层是

deque

，支持两端操作，但 SPFA 只需 FIFO，所以无需改用

list

——那会增加指针跳转开销常见编译/运行错误怎么快速定位最常踩的坑不是算法错，而是边界没控住或初始化遗漏，导致未定义行为或 WA。立即学习 “ C++免费学习笔记（深入） ”；

dist[]

初始化必须用

LLONG_MAX / 0x3f3f3f3f

，不能用

-1

或

0

—— 否则负权边松弛时比较失效忘记清空

in_queue[]

和

cnt[]

数组（多测时尤其致命），导致上一组数据残留影响下一组邻接表遍历时写成

for (int i = head[u]; i; i = nxt[i])

，但忘了初始化

head[]

全为

0

，结果第一次就跳进野地址报

runtime error: signed integer overflow

？大概率是

dist[u] + w

溢出，加个

if (dist[u] != LLONG_MAX)

再算 SPFA 的核心约束其实就两条：入队要受控，更新要严格按松弛条件。一旦放松这两点，它就退化成不可预测的 BFS 式乱搜。真正难的不是写出来，是写完后敢不敢删掉所有“以防万一”的冗余判断。

相关文章