贝尔曼-福特算法

贝尔曼-福特算法与戴克斯特拉算法相似,它被用于寻找有向加权图中来源节点到所有其他节点的最短路线。两个算法不同的一点是后者要求权重不为负,而前者则没有此要求。不过注意,虽然贝尔曼-福特算法中权重可为负,但是它要求图中不存在负权回路,因为反复遍历回路可令距离值不断缩小,因此陷入无限循环,例如,图 1 中的两个图不满足条件。
不满足要求的图
图 1:不满足要求的图

戴克斯特拉算法每一次都选取距离值最小的未固定节点,将其边进行松弛,而贝尔曼-福特算法只是简单地对所有边进行 n-1 次松弛,n 为节点数量。因为更简单,所以贝尔曼-福特算法的时间复杂度高于戴克斯特拉算法。它的时间复杂度为 O(|v||E|),|v| 为节点数量,|E| 为边数量。

1. 算法介绍

1) 第一步:选择 A 为来源节点。设 A 的距离值为 0,其余节点的为最大值,如图 2 所示。
贝尔曼-福特例图(1)
图 2:贝尔曼-福特例图(1)

用例表来记录并更新每一个节点的距离值,如图 3 所示。
贝尔曼-福特例表(1)
图 3:贝尔曼-福特例表(1)

2) 第二步:依次松弛所有的边,顺序随意。我们选择顺序为 AB、AC、BD、CA、CB、CE、DE、DF、FD、FE。松弛的意思不变:比较两个值,一个是边起点的距离值加边的权重,另一个是边终点的距离值。如果前者小,就更新后者为前者。
  • 松弛 AB:0+-2<MAX,B 的新距离值等于 -2。
  • 松弛 AC:0+0<MAX,C 的新距离值等于 0。
  • 松弛 BD:-2-3<MAX,D 的新距离值等于 -5。
  • 松弛 CA:0+0=0,不更新 A 的距离值。
  • 松弛 CB:0-2=-2,不更新 B 的距离值。
  • 松弛 CE:0+4<MAX,E 的新距离值等于 4。
  • 松弛 DE:-5-1<-6,E 的新距离值等于 -6。
  • 松弛 DF:-5+1<MAX,F 的新距离值等于-4。
  • 松弛 FD:-4+1>-5,不更新 D 的距离值。
  • 松弛 FE:-4+2>-6,不更新 E 的距离值。

松弛后如图 4 所示。
贝尔曼-福特例图(2)
图 4:贝尔曼-福特例图(2)

在列表里我们标记被更新节点的前任节点。如果边被成功松弛,那么将边终点的前任节点改为边起点,如图 5 所示。
贝尔曼-福特例表(2)
图 5:贝尔曼-福特例表(2)

3) 第三步:我们一共要松弛所有边 n-1 次,n 为节点数量。本例 n 等于 6,所以我们一共要松弛 5 次。现在进行第二次松弛。松弛顺序随意,为了方便我们一直使用顺序 AB、AC、BD、CA、CB、CE、DE、DF、FD、FE。
  • 松弛 AB:0+2>-2,不更新 B 的距离值。
  • 松弛 AC:0+0=0,不更新 C 的距离值。
  • 松弛 BD:-2-3=-5,不更新 D 的距离值。
  • 松弛 CA:0+0=0,不更新 A 的距离值。
  • 松弛 CB:0-2=-2,不更新 B 的距离值。
  • 松弛 CE:0+4>-6,不更新 E 的距离值。
  • 松弛 DE:-5-1=-6,不更新 E 的距离值。
  • 松弛 DF:-5+1=-4,不更新 F 的距离值。
  • 松弛 FD:-4+1>-5,不更新 D 的距离值。
  • 松弛 FE:-4+2>-6,不更新 E 的距离值。

第二次松弛过后的例图没有改变,如图 6 和图 7 所示。
贝尔曼-福特例图(3)
图 6:贝尔曼-福特例图(3)

贝尔曼-福特例表(3)
图 7:贝尔曼-福特例表(3)

4) 第四步:两次连续得到了同样的结果,意味着当前结果已是最终结果。

利用例表 3 的最后一行查询来最短路线。以 AF 为例,F 的前任节点是 D,D 的前任节点是 B, B 的前任节点是 A,所以 AF 的最短路线是 A→B→D→F,路线距离为 -4。

我们总结贝尔曼-福特算法如下:
  1. 选择来源节点,设来源节点距离值为 0,其余节点距离值为最大值;
  2. 依次松弛所有边;
  3. 重复上一步 n-2 次,n 为节点数量,直到两次连续得到同样的结果。

2. 算法证明

我们依然用数学归纳法来证明贝尔曼-福特算法的正确性。设 s 为来源节点,v 为任意节点。令 Pk(v) 代表第 k 次松弛后 s 到 v 的路线,Ck(v) 代表最多经过 k 条边的,从 s 到 v 的正确最短路线。

证明:在第 k 次松弛后,Pk(v)=Ck(v)。如果证明成功,在第 n-1 次松弛后,Pn-1(v) 肯定是最多经过 n-1 条边的最短路线。因为图中没有负回路,所以最短路线最多经过 n-1 条边,因此,最多经过 n-1 条边的最短路线就是最后的正确最短路线。

1) 证明第一步:当 k 为 0 时,所有节点的路线都未明确,也就是说,P0(v)=空,v 为任何节点。初始情况满足条件,因为 C0(v)=空,毕竟图中没有经过 0 条边的路线。

2) 证明第二步:假定 Pk(v)=Ck(v),v 为任意节点,也就是说,假定从开始一直到第 k 次松弛,算法都做了正确的决定。这意味着在第 k 次松弛后,从 s 到任何 v 的路线都是正确的最多通过 k 条边的最短路线。

3) 证明第三步:证明 Pk+1(v) 是最多通过 k+1 条边的正确路线。也就是说,证明 Pk+1(v)=Ck+1(v)。

假设 Ck+1(v)=s→(某些节点)→u→v,u 是 v 在这条最佳路径上的前任节点。因为最佳路径中的子路径一定也是最佳的,所以我们知道 s→(某些节点)→u=Ck(u),所以,Ck+1(v)=Ck(u)→v。由于我们在第二步假定了 Pk(u)=Ck(u),所以 Ck+1(v)=Pk(u)→v。

在第 k+1 次松弛时,我们依次松弛了所有的边,其中包括 u→v。在松弛 uv 的过程中,我们对比了两个路线,第一个是 Pk(v),第二个是 Pk(u)→v,然后令 Pk+1(v) 为两者中较短的那个路线,这是松弛的定义。第二个选择 Pk(u)→v 等于 Ck+1(v),也就是说,算法比较了 Pk(v) 和 Ck+1(v)。我们需要证明算法令 Pk+1(v)=Ck+1(v)。

一共有以下两种可能:
  1. Pk(v)=Ck+1(v);
  2. Pk(v)≠Ck+1(v)。

如果 Pk(v)=Ck+1(v),那么被对比的两个选择相同,选哪个都是一样的效果,算法令 Pk+1(v)=Pk(v)=Ck+1(v)。

如果 Pk(v)≠Ck+1(v),我们需要证明在所有情况下,Ck+1(v)<Pk(v),只有那样算法才会令 Pk+1(v)=Ck+1(v)。以下是证明:因为 Ck+1(v)≠Pk(v),所以 Ck+1(v) 比 Pk(v) 多了一条边 uv,而 uv 的权重一定为负,所以 Ck+1(v)<Pk(v)。如果 uv 的权重不为负,那么算法在上一次循环时就不会更新 Ck(v) 增长路线,而如果不增长路线,即 Ck+1(v)=Ck(v)=Pk(v),我们就会回到第一种情况。

因此,不论是哪一种可能,我们都可以肯定 Pk+1(v)=Ck+1(v)。也就是说,如果从开始到第 k 次松弛算法都做了正确的决定,那么在第 k+1 次松弛中,算法也一定会做出正确的决定。

4) 证明第四步:如果 Pk(v)=Ck(v),那么 Pk+1(v)=Ck+1(v)。因为 P0(v)=C0(v),所以所有 Pk(v),k>0 都成立,包括 Pn+1(v)。

我们证明了在 n-1 次松弛后,所有节点的最短路线为正确的最短路线。

3. 算法代码

与戴克斯特拉算法相似,我们首先定义图类与构件图的子方法。主方法是 bellmanFord(),其中我们松弛边集合 n-1 次,n 为节点数量。我们也可以加一个判断条件,让程序在特定的情况下提前终止,但是一般来说,直接松弛 n-1 次更方便。最后我们通过前任节点字典获得每一个节点从来源节点开始的最短路线。
import sys
#创建图类,先创建图类对象再运行bellmanford方法
class Graph(): #创建图类
    def __init__(self):
        self.vertices = {} #顶点
        self.edges = []               #边
    #添加边(起点,终点,权重,双向布尔值)
    def addEdge(self, start, end, dist, biDirectFlag = True,):
        if biDirectFlag:                  #双向边
            self.edges.extend([[start, end, dist],[end, start, dist]])
        else:                       #单向边
            self.edges.append([start, end, dist])
    #输出节点集合
    def getVertices(self):
        return set(sum( ([edge[0], edge[1]] for edge in self.edges), [] ))
    #输出所有节点的最短路径和路径距离
    def printSolution(self, dist, predecessor):
        for v in self.vertices :
            path = self.getPath(predecessor, v)        #最短路线
            print (self.src, "to ", v, " - Distance: ", dist[v], " Path - :", path)
    #输出v节点的最短路线
    def getPath(self,predecessor, v):
        pred = predecessor[v]
        path = []
        path.append(v)
        while (pred!= None):
            path.append(pred)
            pred = predecessor[pred]
        path.reverse()
        return(path)
    #最短路径算法
    def bellmanFord(self, src):
        self.src = src
        self.vertices = self.getVertices()
        dist = {v: sys.maxsize for v in self.vertices} #距离值字典
        dist[src] = 0
        predecessor = {                #前任节点字典
            v: None for v in self.vertices
        }
        for i in range(len(self.vertices)-1):      #遍历n-1遍
            for edge in self.edges:            #松弛所有边
                if dist[edge[0]] + edge[2] < dist[edge[1]]:
                    dist[edge[1]] = dist[edge[0]] + edge[2]
                    predecessor[edge[1]]= edge[0]
        self.printSolution (dist, predecessor)
以上为算法代码。以下为实现例图:

graph = Graph()
graph.addEdge("a", "b", 2, False)
graph.addEdge("a", "c", 0, True)
graph.addEdge("c", "b", -2, False)
graph.addEdge("b", "d", -3, False)
graph.addEdge("c", "e", 4, False)
graph.addEdge("d", "e", -1, False)
graph.addEdge("d", "f", 1, True)
graph.addEdge("e", "f", 2, False)
graph.bellmanFord("a")

输出结果:

a to e - Distance: -6 Path - : ['a', 'c', 'b', 'd', 'e']
a to c - Distance: 0 Path - : ['a', 'c']
a to a - Distance: 0 Path - : ['a']
a to b - Distance: -2 Path - : ['a', 'c', 'b']
a to f - Distance: -4 Path - : ['a', 'c', 'b', 'd', 'f']
a to d - Distance: -5 Path - : ['a', 'c', 'b', 'd']