SPFA 思想及局限

一句话理解

SPFA 是队列优化的 Bellman-Ford。

为什么要学

平均快，最坏会被卡成指数。

讲解

竞赛不少数据卡 SPFA。能用 Dijkstra 就别依赖它。仍可用于判负环（入队次数>n）。

例子

只有 dist 变小的点才再入队。

常见错误

• 正权图还用 SPFA 被卡。
• 判负环计数写错。