数据结构（十一）：最短路径(Bellman-Ford算法)@慕课网原创_慕课网

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

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

松弛函数

对边集合 $中任意边，以表示顶点出发到顶点的边的权值，以表示当前从起点到顶点的路径权值$

若存在边 $，使得：$

则更新 $值：$

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

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

松弛函数代码示例

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
        return True    return False

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

松弛函数执行次数

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

digraph

以图 digraph 为例，各顶点之间边的长度如图中所示。以 $表示起点到顶点的距离，以表示起点到顶点的最短路径权值，以表示从顶点到顶点的路径。初始情况，$

从 digraph 图中可以明显发现，若已知 $，则对边执行松弛函数后，即可更新的值。若已更新的值，则对边执行松弛函数后，即可更新的值。$

最好情况下分析：

若遍历松弛的边顺序为： $，其他两条边顺序无影响$

第一次迭代：

对边 $执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则$

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

最坏情况下分析：

若遍历松弛的边顺序为： $或，其他三条边顺序无影响$

第一次迭代：

对边 $执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则$

第一次迭代，有三条边起到了松弛的效果，直观的可以看出 $，第一次迭代可以获得经过一个顶点的最短路径，路径为$

第二次迭代：

对边 $执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则$

第二次迭代，有一条边起到了松弛的效果，直观的可以看出 $，第二次迭代可以获得经过两个顶点的最短路径，路径为$

第三次迭代：

对边 $执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则对边执行松弛函数，则$

第三次迭代，有一条边起到了松弛的效果，直观的可以看出 $，第三次迭代可以获得经过三个顶点的最短路径，路径为，路径如下图所示：$

迭代次数分析：

为了方便后续讨论，对于顶点 $，若已确定，即已确定从起点到该顶点的最短路径权值，这里不妨称该顶点为已确认顶点。后续以路径长度表示从起点到顶点的路径上，经过的顶点个数。例如，对于路径，路径权值为，路径长度为 3。$

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

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

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

注意路径长度和路径权值并无绝对关系，例如若 $的最短路径为，的最短路径为，虽然的路径长度大于，但是的权值并不一定大于。例如上图中，若边的权值为 -2 而不是 2，则的值为 -1，而不是 3，即路径的权值要小于路径。$

推论证明

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

反证说明：

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

则对于任意由起点 $出发到相邻顶点的路径，存在由起点出发经过相邻顶点到达顶点的路径，使得路径的权值小于路径的权值，即可以减小的值。$

若 $，则，路径的权值小于路径的权值，说明路径权值为负数，即图中存在负权回路，与讨论背景不符，如下图所示。$

若 $，对于路径中的部分，因为对于任意相邻顶点，存在，所以同样存在由起点出发经过相邻顶点到达顶点的路径，使得路径的权值小于路径的权值，更新路径为。如此重复，若起点的相邻顶点不为无穷多，则必然在某一时刻，更新路径为，使得路径的权值小于路径的权值，即图中存在负权回路，与讨论背景不符，如下图所示。$

所以对于初始状态的起点 $而言，执行一次迭代后，至少会增加一个已确认顶点。$

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

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

example

作者：zhipingChen
链接：https://www.jianshu.com/p/b876fe9b2338