有个问题

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

YWHHDJSer @ 2024-08-13 07:13:04

在最短路做最优解的题里面，SPFA很容易被卡，但是感觉在那最短路打暴力时，感觉SPFA比Dijkstra的速度明显更高。比如有些删边+判连通性的题，暴力改边权然后跑最短路，SPFA比Dijkstra分高。

by Dangerise @ 2024-08-13 07:41:30

@YWHHDJSer 如果出题人卡spfa，spfa就废

如果不卡spfa，一般比dij快一些

by aCssen @ 2024-08-13 07:42:16

不特殊构造的数据下 SPFA 是 \mathcal{O}(k(n+m)) 的，k 好像在 2 左右。

by czy032321054 @ 2024-08-13 07:42:17

好像SPFA因为最坏情况是O(nm)所以在稀疏图上可能表现更佳吧

by fjy666 @ 2024-08-13 08:08:42

有些题的图是特殊图根本没法卡

by Vsinger_洛天依 @ 2024-08-13 08:18:13

膜拜大佬