disjkstra
- 从队列中选取最短的边
- 以该边的终结点为头进行松弛操作并将终结点标记以便后续不在遍历该点
- 将松弛过的点加入要遍历的队列中
- 重复 1-3 直至遍历完所有结点
bellman-ford
- 遍历边集合,对所有可以进行松弛操作的边进行松弛操作
- 将步骤1重复n次
spfa
- 遍历队列中的点的边进行松弛操作
- 将松弛的点放入队列中
- 重复1-2直至无法更新
差别
- disjkstra基于贪心思想,当有负权边的时候可能得不到正确答案
- bellman-ford 算法可以算出通过k个路径可以到达的点
- spfa算法基于bellman-ford 算法进行优化。bellman-ford算法中未松弛过的点说明已无法松弛,所以后续如果再遍历则是浪费时间,所以spfa对其进行优化将松弛过得点放入队列中,以便后续遍历
- 对于寻找k条路径可以到达的点仍需要使用bellman-ford算法
- 当求负权环的时候,使用spfa算法。需添加一个cnt数组记录到达该点所走过的路径数,当路径大于n时,说明经过了n+1个点。由抽屉原理可得至少有一个点经过了两次
即存在负环。其中dis数组也不需要初始化。因为是求是否有负权环所以一定可以更新dis数组。