理解 Bellman-Ford 算法

如何让计算机在一张地图上找到两个点之间的最短距离？

Bellman-Ford 算法是其中的一个解决方法，但是在使用这个算法之前，我们需要先把地图的信息在计算机里表示出来。

使用 Adjacency List 表示图

Adjacency List 用大白话翻译就是：邻居的列表 —— 用一个列表来记录我有哪些邻居。

用算法导论这本书上的图举个例子。

节点 1 有两个邻居，那么就在第 1 个链表中插入两个链表的 node，来记录下这两个邻居。

在脚本语言中，有很多方法来实现这种表示方式，比如用数组：

adj_list = [
	[2, 5],
	[1, 5, 3, 4],
	[2, 4],
	[2, 5, 3],
	[4, 1, 2]
]

在这个数组中，可以通过 index 来推断节点本身的名字，比如 index == 0 时，节点的名字是 1.

如果觉得这不够直观，也可以用 hash table 类的结构来存储：

adj_list = {
	1: [2, 5],
	2: [1, 5, 3, 4],
	3: [2, 4],
	4: [2, 5, 3],
	5: [4, 1, 2]
}

如果要存储边的权重的数据，可以增加链表节点的属性，对应到脚本语言中，可以在一个数组元素的位置上用一些特殊的数据类型来记录两个数据——一个是邻居的名字，一个是权重：

adj_list = {
	1: [(2, 9), (5, 8)],
	2: [(1, 12), (5, 13), (3, 14), (4, 16)],
	# ...
}

Bellman-Ford 算法

如果一张图有 n 个节点，那么 Bellman-Ford 算法要做的就是对这张图上的所有的边做 n - 1 次松弛（relax）操作。

什么是松弛操作，为什么要进行松弛操作？

在算法的一开始，我们需要给每个点设定一个从指定起始点到达它的距离的估计值：∞ ，即正无穷，或者说假设无法到达；并且设定此节点在来路方向的上一个节点是 nil。用伪代码表示为：

v.distance = ∞
v.previous = nil

然后进行松弛操作：

1. 对于任意一条边 (u -> v)，取出他们存储好的权重 w( u -> v ).
2. 如果 u.distance + w < v.distance，那么做两个赋值操作：v.distance = u.distance + w，v.previous = u；这一步是松弛操作的核心。
3. 如果上面的判断不成立，什么都不做

对每条边得进行一遍这样的操作。但是需要注意的是：u.distance可能等于正无穷，那么u.distance + w还是正无穷，所以u.distance + w < v.distance就变成了两个正无穷的比较。两个正无穷是一样大的，所以在这种情况下，会跳过松弛的核心操作。

当然，这只是第一轮松弛操作，我们要循环做 n - 1 轮，并且最后要判断是否有负权重的环路导致某些节点永远没有最短路径，才算完成 Bellman-Ford 算法，。算法的完整伪代码如下：

# Initialize distance and previous attributes
for v in Graph(v, edges):
	v.distance = ∞
	v.previous = nil
start_point.distance = 0

# Do relaxation for each edge (n - 1) times
while i <= n - 1:
	for u, v in Edge( u -> v)
		if u.distance + w( u -> v ) < v.distance
			v.distance = u.distance + w( u -> v )
			v.previous = u
	i++

# Judge whether there is no negative weight circles in the graph
for u, v in Edge( u -> v)
	if v.distance > u.distance + w( u -> v )
		return False # there is a negative weighted circle
return True # there is no such circle

如果这段程序最后返回的是 True，我们就可以通过取出每个点的 v.distance 来得到这个点到起点的距离，也可以通过取出 v.previous， 以及 v.previous.preivous … 知道起点到这里的路径是什么。（如果 v.distance == ∞，说明无法到达）

为什么这样就可以了？

以上是 Bellman-Ford 的全部动作，但是这样真的可以求出最短路径吗？这的可以判断有没有负权重的环路吗？

我自己在看到这个算法时，想到的第一个问题是：为什么要进行 n - 1 次循环松弛？但我猜《算法导论》的作者知道这会是一些人的问题，所以随后就给出了答案：

做 n - 1 次已经足够了。证明如下：

1. 从原点开始走，到第 x 个节点，这中间只有 x - 1 条边（不考虑环路）
2. 如果一个图有 n 个节点，那么即使用最啰嗦的走法，到达一个点顶多需要走 n - 1 条边（不考虑环路）。也就是顶多把所有的节点都经过一遍。
3. 在第一轮对所有的边进行松弛的时候，被松弛的点其实只有从原点可以一步到达的点。其他的点所在的边 Edge( u -> v ) 中，u.distance 都是 ∞，v 无法被松弛。只有 start_point.distance 为 0，Edge( start_point -> v ) 中的 v 才可能被松弛。
4. 以此类推，在第 i 轮中，被松弛的点只可能是距离原点 i 步的点。他们利用到的边是 Edge( v_{i - 1} -> v_i)，其中 v_{i - 1} 在上一轮松弛的过程中已经被松弛过，如果他能到达原点的话，v_{i - 1}.distance 就不会是 ∞。
5. 有些点可能有多种不同的到达方式，并且在第 i 步之前也松弛过。这其实没关系。如果第 i 步是最后一次到达他，所有能用来到达这个点的边都已经被计算机探索过（不然这就不是最后一次到达），所以这次松弛也将是它最后一次被松弛，之后到达他的 distance 就已经是最终结果值了。
6. 根据上面提到的 2，不可能有节点出现 n - 1 步还到达不了的地方，即使一个点有多条路径可以到达（除非这个点真的无法到达），他的最多步数路径上的边也都被计算机探索过了。也就是说，他的最后一次被访问已经发生过，他的 distance 肯定已经是最终结果值了。没有任何一个点可以例外。

所以 n - 1 次循环已经足够。

如果这 n - 1 次循环确实能把所有点的最终 distance 和 previous 计算出来，那么自动证明 Bellman-Ford 算法可以找到最短路径。

但接下来还有一个问题，如果图中有负权重的回路怎么办？Bellman-Ford 算法能发现我们的路径规划可能深陷在某个回路之中吗？

我们来看看这段做判断的伪代码：

for u, v in Edge( u -> v )
	if v.distance > u.distance + w( u -> v )
		return False # there is a negetive weight circle
return True # there is no such circle

举一个特例来说明这段代码的作用：

在这张图中，c，d，e 构成了一个负权重的回路。在 n - 1 次，也就是 4 次松弛操作后，3号节点会是最后一次松弛操作改变的对象，他的 distance 变为 0。所以在计算机利用 Edge( c -> d )这条边做判断时，d.distance > c.distance + w( c -> d) 就会返回 True，程序就会执行 return False。更完整的证明可以在《算法导论》第380页找到。

总结一下：Bellman-Ford 算法可以用 n - 1 次松弛操作来找到各个点的最短路径，如果那些点存在最短路径的话；也能让负权重回路显形。

后话

你说，算法中的那个操作为什么要叫「松弛」呢？

根据我们之前对 n - 1 次松弛操作的作用的证明，可以想像，在一遍一遍的循环中，最短路径由假设的 ∞，逐渐减小到最终的结果值。这就好像是一个用 ∞ 距离撑起来的图，最开始张力非常大，马上就要撑爆了的感觉；然后一点一点的释放这些张力，让整个图「松弛」下来。

从这个角度讲，最开始设定估计值为 ∞ 的过程如果叫初始化就太抽象了，叫「紧绷」操作或许更形象。

哈哈。