经典图论算法回顾之Bellman-Ford算法

Dijkstra最短路径算法存在的一个问题是不能处理负权图（详见：经典图论算法回顾之Dijkstra算法。今天要回顾的Bellman-Ford算法（wikipedia：Bellman–Ford algorithm）可以求出有负权图的最短路径，并可以对最短路不存在（负权回路）的情况进行判断。

在这里插入图片描述

图1 Richard Ernest Bellman 1920-1984

一、Bellman-Ford算法

不同于Dijkstra算法基于点的操作，Bellman-Ford算法则是基于边的操作。算法的核心思想是不断地对边进行松弛（Relax）操作，松弛操作定义如下：

 RELAX(u, v, w)if v.d > u.d + w(u,v)v.d = u.d + w(u,v)v.p = u

上述代码用于松弛边 $e = (u, v)$ 。其中， $v . d$ 和 $u . d$ 分别是 $u, v$ 到源点的最短距离的估计值，这一值将会逐步逼近最短距离， $w (u, v)$ 表示边的权重， $v . p$ 表示 $v$ 的潜在的最短路径上的前驱节点，用于得到最终得到某一节点的最短路径。

接下来，整个Bellman-Ford算法的伪代码如下：

 BELLMAN-FORD(G,w,s)INITIALIZE-SIGNAL-SOURCE(G,s)   //初始化操作：s.d = 0, (V-s).d = ∞for i=1 to |G.V|-1             //重复执行 |G.V| -1 次for each edge(u,v) in G.E  //对每条边进行松弛操作RELAX(u,v,w)for each edge(u,v) in G.E      //检测是否存在边还可以继续松弛if v.d > u.d + w(u,v)      //如果存在，则有负权回路，不存在最短路径return FALSEreturn TRUE

接下里给出一个简单的示例。如图1(a)所示，我们要求源点 $S$ 到其它各点的最短路径，图1(b)是初始化结果（除了源点外，其他点到源点的最短距离初始化为无穷大）。

我们指定按 $(C, D), (B, D), (A, C), (A, B), (A, D), (B, C), (S, B), (S, A)$ 的顺序依次松弛各条边。
在这里插入图片描述

图1 (a) 给定的图，(b) 初始化结果

第1轮松弛：我们发现， $(C, D), (B, D), (A, C), (A, B), (A, D), (B, C)$ 均无法松弛，只有 $(S, B)$ 和 $(S, A)$ 可以被松弛，松弛结果如下(圆圈中的数字表示到源点的最短路径距离的估值)：

在这里插入图片描述

图2 第1轮松弛结果

第2轮松弛： $(C, D)$ 无法被松弛，我们松弛 $(B, D), (A, C), (A, B)$ ，松弛结果如下：

在这里插入图片描述

图3 第2轮松弛 (B,D),(A,C),(A,B) 的结果

我们接下来松弛 $(A, D), (B, C)$ ，松弛结果如下：
在这里插入图片描述

图4 第2轮松弛 (A,D),(B,C) 的结果

最后松弛 $(S, B), (S, A)$ , 这两条边也无法继续松弛。

后续进行的第3轮和第4轮实际上已经无法急促松弛，最终得到的结果如下：
在这里插入图片描述

图5 最终结果（最短路径树）

二、算法正确性

为什么该算法可以得到正确的结果呢？下面就不严谨地解释一下。

2.1 收敛性性质

收敛性如下图所示(图片来自于：https://zhuanlan.zhihu.com/p/585315996）：
在这里插入图片描述
也就是说，如果某个点 $v$ 的前驱节点 $u$ 已经在最短路径上，那么, $s\rightsquigarrow u \rightarrow v$ 一定是 $s$ 到 $v$ 的最短路径，且在之后这个最短路径值不再改变。

我们结合上图给出一个例子。这里我们将图1和图5搬下来，其中图5是图1的最短路径树。
在这里插入图片描述

图6 图1及其对应的最短路径树（粗边表示树边）

1）在第1轮松弛中，我们在松弛 $(S, B), (S, A)$ 时，得到了 $d (s, A) = 2$ , $d (s, B) = 6$ ，可以发现 $S\rightarrow B$ 并未在最短路径树上, 因此可能在后续松弛过程中被更新。

2）在第2轮松弛中，我们在松弛 $(A, B)$ 时，得到了 $d (s, B) = 5$ 。此时， $B . p = A$ （ $B$ 的前驱节点更新为 $A$ ）且 $S\rightarrow A$ 已经在最短路径上。为此，进一步确定 $B$ 的最短路径： $S\rightarrow A\rightarrow B$ ，最短距离 $d (S, B) = 5$ 。在后续的松弛操作中， $B$ 的最短路径将保持不变，因为没有更短的距离了。

在算法执行过程中，无论边的松弛顺序如何，在第1轮松弛过程中，总能确定最短路径树上跟源点 $S$ 直接相连的点 $U$ 的最短距离。在第2轮松弛过程中，总能确定那些跟 $U$ 相邻点的最短距离。依此类推，就可以得到所有点的最短距离。

2.2 为什么要执行 $∣ G . V ∣ - 1$ 轮松弛

如图1所示的图，我们仅执行2轮松弛操作就可以得到最终结果，那么为什么要执行 $∣ G . V ∣ - 1$ 轮松弛呢？

这是基于最坏情况考虑的，如果某个图如下所示，边的松弛顺序为 $(v_{n-1},v_n), \cdots (v_2,v_3), (v_1,v_2)$ ，那么每次只能从前往后确定一个顶点的最短路径，因此确实需要 $∣ G . V ∣ - 1$ 轮松弛操作才能得到最终结果。
在这里插入图片描述

图7 退化成单链的图

2.3 改进策略 SPFA

针对图7所示的单链表式的图，按照上述给定的边松弛顺序，我们确实需要 $∣ G . V ∣ - 1$ 轮松弛才能得到最终结果。那么如何改进呢？针对上图，我们如果从前往后更新似乎一轮松弛就可以得到最终结果。

为此，SPFA应运而生，该算法可以看做最短路径跟BFS的结合。它从源点开始，逐步向外松弛邻接点，相当于大体指定了边的松弛顺序，从而提升速度。

这里就不再讲述SPFA，具体可以参见：知乎：算法系列——四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA。

三、处理负权图

接下里，我们用图8来说明Bellman-Ford处理负权图的能力。

对于上面的case，假设 $v_0$ 为源点，给定边的松弛顺序为: $v_3,v_4)$ , $v_1,v_3)$ , $v_1,v_2)$ , $v_0,v_1)$ , $v_0,v_2)$ 。
第1轮松弛后，可以得到： $d(v_0,v_1) = 4$ , $d(v_0,v_2) = 2$ 。
在第2轮松弛过程中，当松弛 $v_1,v_2)$ 时，可以得到： $d(v_0,v_2) = 4+(-3)=1$ 。
对于下面的case，无论以何种松弛顺序，在4轮松弛后， $v_1,v_2,v_3,v_4$ 到源点的最短路径均可更新。为此，通过Bellman-Ford算法的最后一次环路检测就可以判别出来。