经典图论算法回顾之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⇝u\to v$ 一定是 $s$ 到 $v$ 的最短路径，且在之后这个最短路径值不再改变。

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

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

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

2）在第2轮松弛中，我们在松弛$(A,B)$ 时，得到了 $d(s,B)=5$。此时， $B.p=A$（$B$的前驱节点更新为$A$）且 $S\to A$ 已经在最短路径上。为此，进一步确定$B$的最短路径：$S\to A\to 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算法的最后一次环路检测就可以判别出来。

图8 Bellman-Ford算法可以处理负权图

四、结语

本文简单回顾了Bellman-Ford最短路径算法的思想，以及不严谨的说明了算法的正确性。鉴于作者水平，如有不正确之处，还请读者批评指正！

参考资料

[1] wikipedia:Bellman–Ford algorithm
[2] 知乎：图解Bellman-Ford计算过程以及正确性证明
[3] 知乎：算法系列——四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA