(代码随想录)BEllman_ford算法 及其优化 SPFA

代码随想录

(知识提炼)

Bellman_ford算法

用处

解决带负权值的单源最短路问题

核心思想

 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

何为松弛

minDist[B] 表示 到达B节点 最小权值，minDist[B] 有哪些状态可以推出来？

状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）

 则   通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

为何是松弛n - 1次?

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。(这里建议看原文去理解,单看这个不好理解)

算法题秒杀思路(用于解决什么问题)

求得目标最短路径

SPFA   

即  Bellman_ford队列优化算法

优势

只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了

用队列来记录上次松弛的时候更新过的节点。（其实用栈也行)

拓展

有正权回路也没关系,使用队列优化，有元素重复加入队列，也会因为最后 minDist数组 不会在发生变化而终止。

应用

bellman_ford之判断负权回路

代码随想录

在 bellman_ford 算法中，松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径，松弛 n 次以上，minDist数组（记录起到到其他节点的最短距离）中的结果也不会有改变 .

有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变.

法一:使用Bellman_ford算法再多松弛一次.

法二:使用SPFA算法,判断如果重复加入队列的某元素次数超过了极限n - 1次(在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。)就代表存在负权回路.

bellman_ford之单源有限最短路

代码随想录

即限制节点数.

原算法是"节点数量为n，起点到终点，最多是 n-1 条边相连。 那么对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。"

而这里是"最多经过 k 个城市， 那么是 k + 1条边相连的节点",即在Bellman_ford算法中缩减松弛的次数就行,缩减为k + 1次

注意:但其实,每一次松弛的过程中,由于我们便利的是整个mindist数组,那么就不可避免的会有很多个节点进行了松弛,我们需要进行k次松弛,但是每一次松弛则松弛了不只一个节点,这就是问题所在,

因此,万能的卡尔提出了使用minDist_copy来记录上一次松弛后minDist数组,并且当下minDist数组的改变完全依据上一次松弛后的minDist,这就真正实现了每次松弛时不会依据本次已经松弛后的节点进行改变.(感觉自己讲的还是有点云里雾里,还是看原文好理解一点)