稠密图用朴素版dijkstra算法,稀疏图用堆优化版的
不是所有能用bellman-ford算法都能用SPFA,bpfa有时候会被卡常
最短路算法问题不会让你证明正确性,考察的侧重点是建图建模,如果把原问题抽象成最短路问题。
有负权回路的话,最短路不一定存在。
bellman-ford算法也可以用来找负环,只要在最后一重循环判断是否有更新,这里要理解第k重循环的意义。不过一般判断是否有负环用spfa算法。
spfa算法要求图中没有负环,只要图中没有负环就可以用spfa。
dijkstra算法要求没有负权边。
要求最多只能经过k条边,那存在负环也还是会有最短路径,所以bellman-ford算法不要求没负环。
为什么bellman-ford算法要开一个backup
?和0-1背包问题要倒着遍历的理由一样。
为什么bellman-ford算法里最后判断某个点是否不可达用> INF / 2
判断?比如,
dist[5] = INF, dist[6] = INF, 5 --> 6有条权为-2的边,
那么dist[6] = min(dist[6], dist[5] + (-2))就会把dist[6]更新地比INF小。
图论的题别忘了初始化为0和INF
memcpy(backup, dist, sizeof(dist)); //参数别反了
下图中各个算法什么时候用,时间复杂度要记得。
SPFA算法
spfa算法和dijkstra算法、拓扑排序算法的思路一样,相当于是用bfs优化了bellman-ford算法。
把点加入队列和拿出队列的时候记得更新判断这个点是否在队列中的数组inQ,这点和普通的bfs一致。
如果对无负环的题用spfa被卡常了,得换成堆优化版dijkstra算法。
判断是否存在负环
spfa和bellman-ford都行,二者思路一样,spfa更快。
思路:每次更新dist[x]的时候把cnt[x]加一cnt[j]= cnt[t] + 1
,cnt[x]表示从源点到点x最短路径上的边数,如果cnt[x] >= n,由抽屉原理,存在两个点在该最短路径上,即存在负环。
只判断是否存在负环的话,dist可以不初始化,因为我们不关心它的绝对值,只关心它的相对值。
一开始要把所有点都加入队列,而不是只有“源点O”,因为不是“判断是否在O到其它点的最短路径上存在负环”
BPFA是啥?
spfa写错了233