最短路径是指连接图中两个顶点的路径中,所有边构成的权值之和最小的路径。之前提到的广度优先遍历图结构,其实也是一种计算最短路径的方式,只不过广度遍历中,边的长度都为单位长度,所以路径中经过的顶点的个数即为权值的大小。
最短路径中不能包含负权回路,因为每次经过负权回路,路径的权值会减少,所以这种情况下不存在最短路径。有些图结构中会存在负权边,用于表达通过某条途径可以降低总消耗,在有向图中,负权边不一定会形成负权回路,所以在一些计算最短路径算法中,负权边也可以计算出最短路径;在无向图中,负权边就意味着负权回路,所以无向图中不能存在负权边。后续的所有讨论都设定图中不存在负权回路的情况。
对边集合
中任意边,以
表示顶点
出发到顶点
的边的权值,以
表示当前从起点
到顶点
的路径权值
若存在边
,使得:
则更新
值:
所以松弛函数的作用,就是判断是否经过某个顶点,或者说经过某条边,可以缩短起点到终点的路径权值。
为什么将缩短距离的操作称之为“松弛”,不妨理解为,选择某种方式后,到达目的的总代价降低了。什么名字无关紧要,不必纠结。
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
算法的执行过程很简单,就是对边集合进行
次迭代松弛,执行结束后,若返回值为 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
函数用于从邻接矩阵中转换出边的集合。代码中第一个循环内包含一个嵌套循环,用于对边集执行
次迭代松弛,第二个循环用于执行第
次迭代,判断是否发生更新最短路径权值的情况,若发生更新权值,则表示图中存在负权回路。
Bellman-Ford
算法中共存在
次对边集合的迭代松弛,边集合的大小为
,所以Bellman-Ford
算法的时间复杂度为
。
代码及测试
github
链接:最短路径