SPFA 算法的用途与优缺点
哪些公司问过
答案要点
- SPFA 是 Bellman-Ford 的队列优化,求单源最短路,支持负权边
- 只把距离被更新的点入队再松弛其出边,减少无效松弛
- 判负环:某点最短路边数达到 n,或入队次数达到 n
- 优点:实现简单、能判负环,随机图上平均很快
- 缺点:最坏 O(VE),易被网格图等构造数据卡;无负权时优先堆优化 Dijkstra
易错点
- 认为 SPFA 复杂度是 O(kE) 且 k 很小,忽略最坏 O(VE)
- 无负权图也用 SPFA,被构造数据卡超时
- 判负环只看从起点可达的部分,误判全图无负环
面试官常见追问
- 为什么 Dijkstra 不能处理负权边?
- SPFA 和 Bellman-Ford 复杂度对比?
- 有向图有负环,从起点到不了它,会被判出来吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。