SPFA 是 $O(n log n)$
dijkstra 是 $O(n)$
by chuxm @ 2024-02-16 11:05:52
n 是点数
by chuxm @ 2024-02-16 11:06:25
但对于这题好像不对啊
by chuxm @ 2024-02-16 11:07:51
@[chuxm](/user/994729) 您在说什么啊。
SPFA 是 $O(nm)$ 的，但是在没有特意构造数据卡的情况下跑得很优秀。
Dij 是 $O(n\log m)$（二叉堆优化）$O(m+n\log n)$（更高级的优先队列优化）。
by HarmonicQuadrilatera @ 2024-02-16 11:17:19
@[HarmonicQuadrilatera](/user/648933)
妈的，脑抽了，我的问题，那个是排序和插入
by chuxm @ 2024-02-16 11:23:09
图上 SPFA 老师死活不讲，现在只会 Dijkstra 了
by chuxm @ 2024-02-16 11:24:31
只记得 SPFA 比 Dijstra 跑的慢了
by chuxm @ 2024-02-16 11:25:09
@[HarmonicQuadrilatera](/user/648933) Dij是 $O(mlogn)$ 吧
by sansesantongshun @ 2024-02-24 13:39:45
@[sansesantongshun](/user/866613) 是（艹手滑打错了抱歉抱歉）
by HarmonicQuadrilatera @ 2024-02-24 17:15:17