经典图论算法回顾之Bellman-Ford算法
经典图论算法回顾之Bellman-Ford算法
Bellman-Ford算法是图论中用于寻找最短路径的经典算法之一，尤其适用于处理包含负权边的图。本文将详细介绍该算法的基本思想、实现步骤、正确性证明以及其在处理负权图时的独特优势。
Dijkstra最短路径算法存在的一个问题是不能处理负权图（详见：经典图论算法回顾之Dijkstra算法。今天要回顾的Bellman-Ford算法（wikipedia：Bellman–Ford algorithm）可以求出有负权图的最短路径，并可以对最短路不存在（负权回路）的情况进行判断。
图1 Richard Ernest Bellman 1920-1984
一、Bellman-Ford算法
不同于Dijkstra算法基于点的操作，Bellman-Ford算法则是基于边的操作。算法的核心思想是不断地对边进行松弛（Relax）操作，松弛操作定义如下：
def 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 ) e = (u,v)e=(u,v)。其中，v . d v.dv.d和u . d u.du.d分别是u , v u,vu,v到源点的最短距离的估计值，这一值将会逐步逼近最短距离，w ( u , v ) w(u,v)w(u,v)表示边的权重，v . p v.pv.p表示v vv的潜在的最短路径上的前驱节点，用于得到最终得到某一节点的最短路径。
接下来，整个Bellman-Ford算法的伪代码如下：
def 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 FALSE
return TRUE
接下来给出一个简单的示例。如图1(a)所示，我们要求源点S SS到其它各点的最短路径，图1(b)是初始化结果（除了源点外，其他点到源点的最短距离初始化为无穷大）。
我们指定按( C , D ) , ( B , D ) , ( A , C ) , ( A , B ) , ( A , D ) , ( B , C ) , ( S , B ) , ( S , A ) (C,D),(B,D),(A,C),(A,B),(A,D),(B,C),(S,B),(S,A)(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 ) (C,D),(B,D),(A,C),(A,B),(A,D),(B,C)(C,D),(B,D),(A,C),(A,B),(A,D),(B,C)均无法松弛，只有( S , B ) (S,B)(S,B)和( S , A ) (S,A)(S,A)可以被松弛，松弛结果如下(圆圈中的数字表示到源点的最短路径距离的估值)：
图2 第1轮松弛结果
第2轮松弛：( C , D ) (C,D)(C,D)无法被松弛，我们松弛( B , D ) , ( A , C ) , ( A , B ) (B,D),(A,C),(A,B)(B,D),(A,C),(A,B)，松弛结果如下：
图3 第2轮松弛 (B,D),(A,C),(A,B) 的结果
我们接下来松弛( A , D ) , ( B , C ) (A,D),(B,C)(A,D),(B,C)，松弛结果如下：
图4 第2轮松弛 (A,D),(B,C) 的结果
最后松弛( S , B ) , ( S , A ) (S,B),(S,A)(S,B),(S,A), 这两条边也无法继续松弛。
后续进行的第3轮和第4轮实际上已经无法进一步松弛，最终得到的结果如下：
图5 最终结果（最短路径树）
二、算法正确性
为什么该算法可以得到正确的结果呢？ 下面就不严谨地解释一下。
2.1 收敛性性质
收敛性如下图所示(图片来自于：https://zhuanlan.zhihu.com/p/585315996）：
也就是说，如果某个点v vv的前驱节点u uu已经在最短路径上，那么,s ⇝ u → v s\rightsquigarrow u \rightarrow vs⇝u→v一定是s ss到v vv的最短路径，且在之后这个最短路径值不再改变。
我们结合上图给出一个例子。这里我们将图1和图5搬下来，其中图5是图1的最短路径树。
图6 图1及其对应的最短路径树（粗边表示树边）
1）在第1轮松弛中，我们在松弛( S , B ) , ( S , A ) (S,B),(S,A)(S,B),(S,A)时，得到了d ( s , A ) = 2 d(s,A) = 2d(s,A)=2,d ( s , B ) = 6 d(s,B) = 6d(s,B)=6，可以发现S → B S\rightarrow BS→B并未在最短路径树上, 因此可能在后续松弛过程中被更新。
2）在第2轮松弛中，我们在松弛( A , B ) (A,B)(A,B)时，得到了d ( s , B ) = 5 d(s,B) = 5d(s,B)=5。此时，B . p = A B.p = AB.p=A（B BB的前驱节点更新为A AA）且S → A S\rightarrow AS→A已经在最短路径上。为此，进一步确定B BB的最短路径：S → A → B S\rightarrow A\rightarrow BS→A→B， 最短距离d ( S , B ) = 5 d(S,B) = 5d(S,B)=5。在后续的松弛操作中，B BB的最短路径将保持不变，因为没有更短的距离了。
在算法执行过程中，无论边的松弛顺序如何，在第1轮松弛过程中，总能确定最短路径树上跟源点S SS直接相连的点U UU的最短距离。在第2轮松弛过程中，总能确定那些跟U UU相邻点的最短距离。 依此类推，就可以得到所有点的最短距离。
2.2 为什么要执行∣ G . V ∣ − 1 |G.V|-1∣G.V∣−1轮松弛
如图1所示的图，我们仅执行2轮松弛操作就可以得到最终结果，那么为什么要执行∣ G . V ∣ − 1 |G.V|-1∣G.V∣−1轮松弛呢？
这是基于最坏情况考虑的，如果某个图如下所示，边的松弛顺序为( v n − 1 , v n ) , ⋯ ( v 2 , v 3 ) , ( v 1 , v 2 ) (v_{n-1},v_n), \cdots (v_2,v_3), (v_1,v_2)(vn−1 ,vn ),⋯(v2 ,v3 ),(v1 ,v2 )， 那么每次只能从前往后确定一个顶点的最短路径，因此确实需要∣ G . V ∣ − 1 |G.V|-1∣G.V∣−1轮松弛操作才能得到最终结果。
图7 退化成单链的图
2.3 改进策略 SPFA
针对图7所示的单链表式的图，按照上述给定的边松弛顺序，我们确实需要∣ G . V ∣ − 1 |G.V|-1∣G.V∣−1轮松弛才能得到最终结果。 那么如何改进呢？ 针对上图，我们如果从前往后更新似乎一轮松弛就可以得到最终结果。
为此，SPFA应运而生，该算法可以看做最短路径跟BFS的结合。它从源点开始，逐步向外松弛邻接点，相当于大体指定了边的松弛顺序，从而提升速度。
这里就不再讲述SPFA，具体可以参见：知乎：算法系列——四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA。
三、处理负权图
接下来，我们用图8来说明Bellman-Ford处理负权图的能力。
对于上面的case，假设v 0 v_0v0 为源点， 给定边的松弛顺序为:( v 3 , v 4 ) (v_3,v_4)(v3 ,v4 ),( v 1 , v 3 ) (v_1,v_3)(v1 ,v3 ),( v 1 , v 2 ) (v_1,v_2)(v1 ,v2 ),( v 0 , v 1 ) (v_0,v_1)(v0 ,v1 ),( v 0 , v 2 ) (v_0,v_2)(v0 ,v2 )。
第1轮松弛后，可以得到：d ( v 0 , v 1 ) = 4 d(v_0,v_1) = 4d(v0 ,v1 )=4,d ( v 0 , v 2 ) = 2 d(v_0,v_2) = 2d(v0 ,v2 )=2。
在第2轮松弛过程中，当松弛( v 1 , v 2 ) (v_1,v_2)(v1 ,v2 )时，可以得到：d ( v 0 , v 2 ) = 4 + ( − 3 ) = 1 d(v_0,v_2) = 4+(-3)=1d(v0 ,v2 )=4+(−3)=1。
对于下面的case，无论以何种松弛顺序，在4轮松弛后，v 1 , v 2 , v 3 , v 4 v_1,v_2,v_3,v_4v1 ,v2 ,v3 ,v4 到源点的最短路径均可更新。 为此，通过Bellman-Ford算法的最后一次环路检测就可以判别出来。
图8 Bellman-Ford算法可以处理负权图
四、结语
本文简单回顾了Bellman-Ford最短路径算法的思想，以及不严谨的说明了算法的正确性。鉴于作者水平，如有不正确之处，还请读者批评指正！
参考资料
[1]wikipedia:Bellman–Ford algorithm
[2]知乎：图解Bellman-Ford计算过程以及正确性证明
[3]知乎：算法系列——四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA