关于堆优spfa

P4779 【模板】单源最短路径（标准版）

枫之都 @ 2024-11-27 18:18:40

代码 and 提交记录

注意这不是讨论区题解

萌新写完 \mathtt{dijkstra} 和 \mathtt{SPFA} 后尝试把 \mathtt{SPFA} 中的队列改成堆，然后意外地发现这玩意在两道模板题中跑的都比~~自己的~~ \mathtt{dijkstra} 快，这是有什么原因吗

另外，这种算法有时间复杂度保证吗？

by Grammar__hbw @ 2024-11-27 18:20:47

@枫之都他们是一样的（记得用vis处理一下去过的点）

所以负权图不可用

by lct201714 @ 2024-11-27 18:35:55

堆优化本质是贪心，加上之后SPFA就不能在负权图中使用了。

时间差别约等于dij是否堆优化

by Sunhaisheng2009 @ 2024-11-28 07:48:51

这应该是堆优化BF吧@枫之都