数据结构（十一）：最短路径(Bellman-Ford算法)

zhipingChen

发布于 2018-12-11 17:11:43

2K0

最短路径是指连接图中两个顶点的路径中，所有边构成的权值之和最小的路径。之前提到的广度优先遍历图结构，其实也是一种计算最短路径的方式，只不过广度遍历中，边的长度都为单位长度，所以路径中经过的顶点的个数即为权值的大小。

最短路径中不能包含负权回路，因为每次经过负权回路，路径的权值会减少，所以这种情况下不存在最短路径。有些图结构中会存在负权边，用于表达通过某条途径可以降低总消耗，在有向图中，负权边不一定会形成负权回路，所以在一些计算最短路径算法中，负权边也可以计算出最短路径；在无向图中，负权边就意味着负权回路，所以无向图中不能存在负权边。后续的所有讨论都设定图中不存在负权回路的情况。

松弛函数

对边集合

中任意边，以

表示顶点

出发到顶点

的边的权值，以

表示当前从起点

到顶点

的路径权值

若存在边

，使得：

则更新

值：

所以松弛函数的作用，就是判断是否经过某个顶点，或者说经过某条边，可以缩短起点到终点的路径权值。

为什么将缩短距离的操作称之为“松弛”，不妨理解为，选择某种方式后，到达目的的总代价降低了。什么名字无关紧要，不必纠结。

松弛函数代码示例

def releax(edge, distance, parent):
    if distance[edge.begin - 1] == None:
        pass
    elif distance[edge.end - 1] == None or distance[edge.end - 1] > distance[edge.begin - 1] + edge.weight:
        distance[edge.end - 1] = distance[edge.begin - 1] + edge.weight
        parent[edge.end - 1] = edge.begin - 1

distance 列表存储从起点到当前顶点的路径权值，parent 列表存储到当前顶点的前驱顶点下标值。初始 distance 列表和parent 列表元素皆为 None，表示路径权值为无穷大，处于不可达状态。

松弛函数执行次数

以对边集合

中每条边执行一次松弛函数作为一次迭代，接下来判断需要执行多少次迭代，可以确保计算出起点到每个顶点的最短距离。

digraph

以图 digraph 为例，各顶点之间边的长度如图中所示。以

表示起点

到顶点

的距离，以

表示起点

到顶点

的最短路径权值，以

表示从顶点

到顶点

的路径。初始情况

，

从 digraph 图中可以明显发现，若已知

，则对边

执行松弛函数后，即可更新

的值。若已更新

的值，则对边

执行松弛函数后，即可更新

的值。

最好情况下分析：

若遍历松弛的边顺序为：

，其他两条边

顺序无影响

第一次迭代：

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

因为图结构比较简单，所以可以直接由观察得知，经过第一次迭代，即得出从起点到各个顶点的最短路径权值。

最坏情况下分析：

若遍历松弛的边顺序为：

或

，其他三条边

顺序无影响

第一次迭代：

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

第一次迭代，有三条边起到了松弛的效果，直观的可以看出

，第一次迭代可以获得经过一个顶点的最短路径，路径为

第二次迭代：

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

第二次迭代，有一条边起到了松弛的效果，直观的可以看出

，第二次迭代可以获得经过两个顶点的最短路径，路径为

第三次迭代：

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

对边

执行松弛函数，则

第三次迭代，有一条边起到了松弛的效果，直观的可以看出

，第三次迭代可以获得经过三个顶点的最短路径，路径为

，路径如下图所示：

迭代次数分析：

为了方便后续讨论，对于顶点

，若已确定

，即已确定从起点到该顶点的最短路径权值，这里不妨称该顶点

为已确认顶点。后续以路径长度表示从起点到顶点

的路径上，经过的顶点个数。例如，对于路径

，路径权值为

，路径长度为 3。

通过前面的示例过程可以推论：

若图中存在未确认的顶点，则对边集合的一次迭代松弛后，会增加至少一个已确认顶点

推论的意思是指，对图中顶点的确认，是以一种波纹扩散的方式进行的，这里增长的扩散半径是指路径中已确认顶点的个数，而不是路径的权值，并且路径中不包含未确认顶点。

注意路径长度和路径权值并无绝对关系，例如若

的最短路径为

，

的最短路径为

，虽然

的路径长度大于

，但是

的权值并不一定大于

。例如上图中，若边

的权值为 -2 而不是 2，则

的值为 -1，而不是 3，即路径

的权值要小于路径

。

推论证明

初始情况下，只有起点

属于已确认顶点，根据邻接表记录，若起点存在相邻顶点，则对边集进行一次迭代松弛后，会增加至少一个已确认顶点。

反证说明：

若一次迭代后，起点

的所有相邻顶点都仍处于未确认状态，即一次迭代后，对于任意相邻顶点

，存在

。

则对于任意由起点

出发到相邻顶点

的路径

，存在由起点

出发经过相邻顶点

到达顶点

的路径

，使得路径

的权值小于路径

的权值，即可以减小

的值。

，则

，路径

的权值小于路径

的权值，说明路径

权值为负数，即图中存在负权回路，与讨论背景不符，如下图所示。

，对于路径

中的

部分，因为对于任意相邻顶点

，存在

，所以同样存在由起点

出发经过相邻顶点

到达顶点

的路径

，使得路径

的权值小于路径

的权值，更新路径

为

。如此重复，若起点

的相邻顶点不为无穷多，则必然在某一时刻，更新路径

为

，使得路径

的权值小于路径

的权值，即图中存在负权回路，与讨论背景不符，如下图所示。

所以对于初始状态的起点

而言，执行一次迭代后，至少会增加一个已确认顶点。

一般性的，当图中已经存在一个或多个已确认顶点时，即图处于任意一种状态，若图中尚存在未确认顶点，则执行一次迭代后，会增加至少一个已确认顶点。

证明过程与上面类似，使用下图作为辅助说明：

example

图中红色顶点表示已确认顶点，黑色顶点表示未确认顶点，红色路径表示由起点

出发到各顶点的最短路径，该图用于辅助理解，所以并未标识边的权值。

对于图中的所有最短路径，以

表示每条最短路径上的最后一个顶点，其中

。若一次迭代后，每个顶点

的相邻顶点中都未增加已确认顶点。则对于每个顶点

的相邻顶点

，路径为

，总会存在经过顶点

及其相邻顶点

到达

的路径

，使得路径

的权值小于路径

的权值。同理，对于路径

中的

部分，总会存在更短的经过顶点

的路径去减少路径权值。因为

，若顶点

的相邻顶点个数不为无穷大，则必然存在负权回路，与讨论背景不符。

所以图处于任意一种状态时，若图中尚存在未确认顶点，则执行一次迭代后，会增加至少一个已确认顶点。

辅助说明：

若某条最短路径上的最后一个顶点存在未确认相邻顶点，经过一次迭代松弛后，若经过该顶点的最短路径上未新增已确认顶点，则无论后续经过多少次迭代松弛，经过该顶点的最短路径上都不会新增已确认顶点，即该条路径已经走到头了。

以上图 example 为例，当前已确认顶点

存在两个未确认相邻顶点

。若执行一次迭代松弛后，并未存在从起点

出发经过

到达

或

的最短路径，则永远不会存在从起点

出发经过

到达

或

的最短路径。

不妨假设经过某次迭代后，存在最短路径为

，即

。因为在上一次的迭代后，

的值已确定，但最短路径

并未添加顶点

，即

，存在悖论。

所以对于任意一条最短路径，若一次迭代后未新增已确认顶点，则该最短路径上不会再新增已确认顶点。

若图中存在由起点不可达的顶点，则这些顶点的初始化状态即为最短路径状态，即初始化时就处于已确认状态。

迭代次数结论

根据之前的结论，若图中存在未确认顶点，则每一次迭代后都会新增加至少一个已确认顶点，即图中某条最短路径长度会至少加一。则要找到从起点出发到各顶点的最短路径权值，极端情况下，图中

个顶点都在一条最短路径上，且松弛边按照最坏情况下进行，即一次只增加一个已确认顶点，则需要执行的迭代次数为

次；另一种极端情况，松弛边按照最好情况下进行，则需要执行的迭代次数为 1 次。

Bellman-Ford 算法

Bellman-Ford 算法计算最短路径的过程中，使用了上述的松弛函数，通过对路径的不断松弛，来逐渐获取最短路径。

Bellman-Ford 算法可以检测带权有向图中是否存在负权回路，根据前面对松弛函数执行次数的分析可知，若图中不存在负权回路，那么即使在最坏情况下，也只需要执行

次迭代松弛，即可获得从起点到各顶点的最短路径。

若图中存在负权回路，当回路较小时，例如顶点自身或者两个顶点之间的负权回路，则在

次迭代过程中，可能多次通过了该负权回路；若回路较大，例如从起点出发，串联所有顶点最后回到起点，即通过

条边构成一个圆形，如下图所示。则

次迭代过程中，可能一次也不会通过该负权回路，但是当再执行一次迭代松弛，即可将

值更新为负值，所以可以多执行一次迭代，通过判断是否更新从起点到某个顶点的最短路径权值，来判断图中是否存在负权回路。

算法过程

Bellman-Ford 算法的执行过程很简单，就是对边集合进行

次迭代松弛，执行结束后，若返回值为 TRUE，则表示已经计算出起点到图中各顶点的最短路径，若返回值为 FALSE，则表示图中存在负权回路。

算法示例

def bellman_ford(graph, start, end):
    distance, parent = [None for i in range(graph.number)], [None for i in range(graph.number)]
    times, distance[start - 1], edges = 1, 0, getEdgesFromAdjacencyList(graph)
    while times < graph.number:
        for i in range(len(edges)):
            releax(edges[i], distance, parent)
        times += 1
    for i in range(len(edges)):
        if distance[edges[i].end - 1] > distance[edges[i].begin - 1] + edges[i].weight:
            return False
    return True

代码中 distance 和 parent 两个列表的作用在上面已经提过了，times 变量用于记录迭代的执行次数，edges 列表是存储边的集合，getEdgesFromAdjacencyList 函数用于从邻接矩阵中转换出边的集合。代码中第一个循环内包含一个嵌套循环，用于对边集执行

次迭代松弛，第二个循环用于执行第

次迭代，判断是否发生更新最短路径权值的情况，若发生更新权值，则表示图中存在负权回路。