(多源最短路径问题)
在本章中,我们考虑如何找到一个图中所有结点之间的最短路径,该问题在计算所有城市之间的交通道路距离时常出现。
我们当然可以运行n次基于贪心的单源最短路径来计算出结果,本章也介绍了一个基于动态规划算法来解决最短路径问题。
1.Floyd-Warshall算法
时间复杂度O(n^3)。
最短路径的结构
如果一条路径是最短路,那么这条路径的任何子路径依然是最短路。所以利用这条我们可以找到动态规划的最优子结构。
所有结点对最短路径问题的递归解
因此我们可以设计出如下递归定义:
初始化为w_ij,之后都进行松弛操作。
自底向上计算最短路径权重
中间矩阵:
代码:
def floyd_warshall(self, graph):
"""
floyd_warshall算法实现,其中graph就是weight
:param graph:
:return:
"""
inf = float('inf')
# 初始化path
path = [[inf for _ in range(len(graph[0]))] for _ in range(len(graph))]
for i in range(len(path)):
for j in range(len(path[0])):
if graph[i][j] != inf and i != j:
path[i][j] = i
for k in range(len(graph)):
for i in range(len(graph)):
for j in range(len(graph[0])):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
path[i][j] = k
return graph, path
构建一条最短路径
需要注意,上述代码最终结果与上图并不完全一致
观察在(0,2)、(1,5)、(4,2)位置均不一样,上图为起始点第二个点的索引,而我的代码是终点前第一个点的所有(即真实路径一个正序输出一个倒序输出,这么做的目的是代码简单)。
2.用于稀疏图的Johnson算法
上述Floyd算法的时间复杂度为O(n^3),当用于稀疏图的时候代价未免过大,本节介绍的Johnson算法的时间复杂度为O(V^2lgV+VE)的算法。
Johnson 算法使用的技术称为重新赋予权重。什么是重新赋予权重呢,字面意思就是重新赋予边的权重。
那么这个算法是什么样子呢?说出来你可能不信,就是进行n次Dijsktra算法(那么为什么是lgV呢,当然是使用改进的Dijsktra,选择的时间由V降为lgV),因为每次Dijsktra结果都会修改当前结点到其他结点的距离,下次计算时,我们就使用上一次的结果作为输入,因此叫重新赋予权重。
0 条评论