dijkstra和spfa相比，那个更好一些

楼上正解。要注意，SPFA的系数k，期望时间复杂度是k<=2，但是，有些时候，某些猥琐的题目会卡你的点。 你可以去SOSO一下这个问题，昨天已经给他答案了：Re: 如果一个图有10W的点，50W的边，用SPFA大约会是… 在没有负权的情况下，Dijkstra是比较好的选择，如果加上堆优化，可以达到很快的速度，并且不会被卡。SPFA尽量少用，不稳定。NOIP3、4题很可能会卡SPFA。

SPFA的时间复杂度其实是在胡扯。在Bellman-Ford的论文里提及了队列优化，也就是现在的SPFA。k八成以上是瞎编的。原论文如下：

算法编程后实际运算情况表明m一般没有超过2n.事实上顶点入队次数m是一个不容易事先分析出来的数,但它确是一个随图的不同而略有不同的常数.所谓常数,就是与e无关,与n也无关,仅与边的权值分布有关.一旦图确定,权值确定,原点确定,m就是一个确定的常数.所以SPFA算法复杂度为O(e)

如果真的如这个所说，单源最短路径的时间复杂度是O（1）。

其实spfa真正复杂度是O（n^2）

带堆优化的dijkstra时间复杂度很低，为O(n logn)，比较一下就可以得出dijkstra更好，不会被卡。

然后呢……在NOI2018 DAY1T1的归程中，spfa被万恶（良心）的出题人卡了，这也意味着以后的比赛将会hack SPFA，所以退spfa入dijkstra+堆优化保平安

我是菜鸡OIer chen_zhe

SPFA在稀疏图上速度很快，但是dijkstra加堆优化之后是稳定的log级别，更稳定。