SPFA判负环
SPFA和Dijkstra都是解决最短路问题的算法,都有各自的特点:
SPFA
:
1.可以判断是否存在负环
2.按层级松弛
3.有些数据可以卡掉SPFA
Dijkstra
:
1.效率稳定
2.不可以解决负边、负环的图
一般处理无负边的最短路问题时,使用Dijkstra。在判断是否存在负环的时候使用SPFA。这里主要讲如何使用SPFA判断正负环。
原理
1.一个n个点的连通图中,经过n-1条边肯定可以到达任意一点。
2.如果存在负环,那么我们一直走这个负环,最短距离是可以无限更新的。
基于上面的原理,我们得到了两种方法判断负环:
DFS:
因为如果有负环的存在,那么松弛操作肯定会在这个负环上无限循环的进行,因此,我们深搜,如果一个点被多次用来松弛更新,那么这个点肯定在负环上。
核心代码:
1 | void dfs(int pos) |
BFS:
基于原理一,如果进行了n-1层松弛之后,存在点还能继续进行松弛,那么肯定存在负环.
核心代码:
1 | queue<int> q; |
判断正环
只需将最短路改成最远路即可。
建议:
1.单纯的求无负权的最短路问题,使用Dijkstra。
2.求负环,最好用DFS,BFS可能会被卡。