SPFA算法与dijkstra算法求单源最短路径的比较

时间:2021-08-02 15:39:32

SPFA是运用队列,把所有的点遍历到没有能更新的,点可以重复入队

如题http://www.cnblogs.com/Annetree/p/5682306.html

dijkstra是每次找出离源点最近的点确定位置,不可重复确定

如题http://www.cnblogs.com/Annetree/p/5675201.html

这样就导致了SPFA可计算负权值而dijkstra不行

例子如图

SPFA算法与dijkstra算法求单源最短路径的比较

1到3

用dijkstra计算为5

用SPFA计算为-2

另外,SPFA可测出负环(如如入队操作超过应有的次数时),但不能输出负环值