Floyd-Warshall算法

Floyd-Warshall算法是一种最短路径算法图．就像bellman算法或者是迪杰斯特拉算法，它计算图中的最短路径。然而，Bellman-Ford和Dijkstra都是单源、最短路径算法。这意味着它们只计算来自单个源的最短路径。另一方面，Floyd-Warshall计算输入图中每对顶点之间的最短距离。

假设你有5个朋友:比利、珍娜、卡西、阿丽莎和哈利。你知道有几条路连接着他们的一些房子，你也知道这些路的长度。但是Floyd-Warshall可以根据你所知道的信息给出最优路线。例如，看看下面的图表，它显示了从一个朋友到另一个朋友的路径和相应的距离。

朋友图

Floyd-Warshall会告诉我们两者的最佳距离每一个一对朋友。它会清楚地告诉你，从Alyssa家到Harry家的最快路径是权重为1的连接边。但是，它也会告诉你，从比利家到珍娜家的最快路线是先经过凯西家，然后是艾莉莎家，然后是哈利家，最后到达珍娜家。这就是弗洛伊德-沃沙尔的力量;不管你现在在哪个房子，它都会告诉你去其他房子的最快路线。

Floyd-Warshall算法就是一个例子动态规划．它将问题分解成更小的子问题，然后结合这些子问题的答案来解决大的初始问题。思路是这样的:要么从A到C的最快路径是目前为止从A到C的最快路径，要么是从A到B的最快路径加上从B到C的最快路径。

Floyd-Warshall在网络中非常有用，类似于最短路径问题的解决方案。然而，由于它可以计算出所有相关节点之间的最短路径，因此在管理路线上的多个站点时更有效。事实上，Floyd-Warshall的一次运行就可以提供你需要知道的关于静态网络的所有信息，从而优化大多数类型的路径。它在计算矩阵逆时也很有用。

Floyd-Warshall的核心是这个功能:

$\text{ShortestPath}(i, j, k)。$

这个函数返回从的最短路径 $一个$来 $C$使用从1到的顶点 $k$在图中。顶点是单独编号的 ${1,2，…k}$．

有一个基本情况和一个递归的情况。基本情况是最短路径就是连接的边的权值 $一个$和 $C:$

$\text{ShortestPath}(i, j, 0) = \text{weight}(i, j)。$

递归的情况将利用动态规划这个问题的本质。这个函数有两种可能的答案。两者之间的最短路径 $我$和 $j$是已知最短路径，还是从这里出发的已知最短路径 $我$到某个顶点(我们叫它 $z$)加上从 $z$来 $珍:$

$\text{ShortestPath}(i, j, k) = \text{min}\big(\text{ShortestPath}(i, j, k-1)， \text{ShortestPath}(i, k, k-1) + \text{ShortestPath}(k, j, k-1)\big)。$

基本上，这个函数设置问的是:"顶点是 $k$最短路径的中间点(除了第一个或最后一个顶点之外的任何顶点)

如果 $k$不是一个中间顶点，那么最短路径从哪里来 $我$来 $j$使用中的顶点 $\{1,2，…, k - 1 \}$也是用顶点的最短路径吗 $\{1,2，…k \}。$

如果 $k$是一个中间顶点，那么路径可以被分解成两条路径，每条路径使用的顶点在 $\{1,2，…, k - 1 \}$中的所有顶点创建一个路径 $\{1,2，…k \}。$这是因为顶点 $k$是中间点。如下图所示。

动态规划分解

Floyd-Warshall算法可以用以下伪代码描述:

12 3 4 5 6 7 8 9 10 11 12 13

创建一个|V| x |V|矩阵M，它将描述顶点之间的距离对于M中的每个单元格(i, j):如果i == j: M[i][j] = 0如果(i, j)是E中的一条边:M[i][j] = weight(i, j) else: M[i][j] =∞对于k从1到|V|:对于i从1到|V|:对于j从1到|V|:如果M[i][j] > M[i][k] + M[k]: M[i][j] = M[i][k] + M[k][j]

Floyd-Warshall算法出现了 $V O \大(| | ^{3}\大)$时间。这是因为三个嵌套为在初始化和填充距离之后运行的循环矩阵, M。

参见:大0符号．

Floyd-Warshall完全依赖于图中顶点的数量。正如你可能猜到的那样，这使得它对某些类型的图特别有用，而对其他类型的图则不太有用。

Floyd-Warshall算法更适合稀疏图还是密集图?(稀疏图是一个没有很多边连接其顶点的图，而密集图有很多边。)

显示答案

Floyd-Warshall算法最适合于密集图，因为它完全不依赖于边的数量。在稀疏图上执行Floyd-Warshall会抹掉它的主要优点。对于稀疏图，约翰逊的算法比较合适。 $_ \广场$

Floyd-Warshall的以下实现是用Python编写的。

在这个实现中，无穷大由一个非常大的整数表示。

12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 44 45 46 47 48 49 50 51 52

类边缘：def__init__（自我，开始，结束，重量）:自我．开始=开始自我．结束=结束自我．重量=重量类图：def__init__（自我）:自我．邻接的=｛｝保存图数据的邻接矩阵自我．vertexCount=0defaddVertex（自我，顶点）:如果顶点在自我．邻接的：返回"顶点已经存在"如果顶点! =自我．vertexCount：返回"不要跳过一个顶点"自我．邻接的(顶点］=[]自我．vertexCount+ =1defaddEdge（自我，开始，结束，重量）:如果开始不在自我．邻接的：返回"起始顶点不在图中"如果结束不在自我．邻接的：返回结束顶点不在图中如果开始＝＝结束：返回"不能有相同的起始和结束顶点"边缘=边缘（开始，结束，重量）自我．邻接的(开始］．附加（边缘）defdoesEdgeExist（自我，开始，结束）:为顶点在自我．邻接的：为边缘在自我．邻接的(顶点]：如果边缘．开始＝＝开始和边缘．结束＝＝结束：返回（真正的，边缘）返回（假，没有一个）deffloydwarshall（自我）:米=[[9999999为x在范围（len（自我．邻接的)))为y在范围（len（自我．邻接的)))为x在范围（len（米)):为y在范围（len（米(0])):如果x＝＝y：米(x] [y］=0存在，边缘=自我．doesEdgeExist（x，y）如果存在：米(x] [y］=边缘．重量为k在范围（len（米)):为我在范围（len（米)):为j在范围（len（米)):newDistance=米(我] [k］+米(k] [j］如果newDistance<米(我] [j]：米(我] [j］=newDistance返回米

的边缘第一行的类是一个简单的对象，它保存有关边缘的信息，如端点和权重。在这个实现中，顶点只是一个简单的整数。的图类使用字典(在第9行初始化)来表示图。这个字典中的键是顶点数，值是边的列表。

的floydwarshall ()函数在第33行创建一个矩阵米．它用每个顶点的最短路径信息填充这个矩阵。例如，从顶点0到顶点2的最短路径距离可以在M [0] [2]．

一般来说，Floyd-Warshall，在最基本的情况下，只提供了结果矩阵中顶点之间的距离。然而，一个简单的改变也可以让算法重建最短路径。有许多不同的方法可以做到这一点，所有这些方法都有内存开销。速度不是路径重建的一个因素，因为重建路径所花费的任何时间与基本算法本身相比都显得微不足道。

最常见的方法是计算一个前导矩阵的序列。在路径计算过程中，即使是矩阵

$P^{(0)}， P^{(1)}，…P ^ {(n)}$

可以计算。 $P ^ {(k)} _ {ij}$定义为顶点的前导 $j$从顶点出发的最短路径 $我$集合中所有的中间点 $1, 2，…k$．因此，对于主循环的每次迭代，都会创建一个新的前导矩阵。

该前代矩阵的递归公式为:

如果 $I = j$或 $\text{weight}(i, j) = \infty, P^{0}_{ij} = 0。$
如果 $I \neq j$和 $\text{weight}(i, j) \lt \infty, P^{0}_{ij} = i。$