关注互联网应用及运维技术的个人博客

Floyd-Warshall算法详解

对于求两点间的最短路径问题,我们通常使用的算法都为迪杰斯特拉算法(无负权边)或者贝尔曼-福特算法(含负权边)。但若是要求解所有结点对之间的最短路径,对以上算法进行穷举往往会造成极大的时间复杂度。以迪杰斯特拉算法来说,对于图 G(V, E) ,该算法的时间复杂度为 O(ElgV),如果需要求任意两点间的最短路径,则需时间复杂度需要乘上一个 E²,即 O(E³lgV),当图为非松散图时,该时间复杂度将变得非常庞大。因此,对于所有结点对之间的最短路径,则都是通过弗洛伊德算法来进行求解,通常时间复杂度为 O(n³)。

该算法在《算法导论》当中也有提到。不过《算法导论》当中的描述确实是过于抽象了,因此在这里我用我自己的理解来讲解一遍,也当是水一篇文章 XD (群里小伙伴都催更了(;´д`)ゞ)

基本思想
弗洛伊德算法是基于动态规划思想来实现的。首先我们需要知道一个定理(算法导论引理 24.1):

对于图 G 当中的两个结点 i 和 j ,他们之间存在一条最短路径 p。若有另外两个结点 a 和 b,这两点位于路径 p 上,则 a 到 b 的最短路径是 p 的子路径。
简单说来,就是最短路径的子路径也是最短路径。

由此我们就可以得到支撑弗洛伊德算法的思想:

如果从 i 到 j 存在最短路径 p( i → j ) ,有另外一个结点 k,如果

k 在 p 上,则 p( i → j ) = p( i → k ) + p( k → j )。p( i → k ) 和 p( k → j ) 为从 i 到 k 的最短路径、从 j 到 k 的最短路径。
弗洛伊德在任意的无负权边的图上都可以应用(与迪杰斯特拉算法一致)。

实现方法
那么我们就来看一下弗洛伊德算法的具体运行方法。

从所有结点当中拿出任意一个结点 k
选出任意一个结点对 [ i, j ]。此时会出现两种情况:
如果 i → j 小于 i → k → j,即若 i 到 j 比 i 通过 k 再到 j 还要小,那么将从 i 到 j 的最短路径更新为 i → k → j
如果 i → j 大于 i → k → j,则不变。
再选出另一对结点对,重复步骤 2,直至所有的结点对都计算了通过 k 后的路径权重。
返回步骤 1,直至所有结点都被拿出来过。
实现这个算法我们通常使用邻接矩阵来表示我们的图,[ i, j ] 在初始化矩阵的时候表示为从 i 到 j 的边的长度。如果 i 到 j 之间无边则为无穷大。

设有 n 个结点,我们需要依次拿出每一个结点,即进行 n 次循环。接着我们要更新每一个结点对的最小路径。由于对于邻接矩阵,[ i, j ] 的值就代表了结点对从 i 到 j 路径的值,因此我们实际上只需要遍历邻接矩阵即可,即需要 n² 的复杂度。其余计算占用的时间复杂度是常数级的,因此这个算法的复杂度为 O(n² * n) = O(n³)。

对于第二步的实现,邻接矩阵为 A,我们实际上就是比较 A[ i ][ j ] 与 A [ i ][ k ] + A[ k ][ j ] 的大小。

以下有一个具体的实现流程可以供大家参考。

弗洛伊德算法是基于动态规划思想实现的。大家可以分析一下,对于每次更新结点对的值时,我们都是使用已经计算过的从 i → k 的值和 k → j 的值。这个与上面的定理是相一致的:即 i → j 的最短路径就是 i → k → j,我们先分别计算出 i → k 和 k → j,然后再将其合并,不就是动态规划嘛。

前驱矩阵
在《算法导论》当中,还引入了一个前驱矩阵这个概念,实际上就是对于最短路径的前驱节点进行一个标注。

在最初,在前驱矩阵 A 当中, [ i, j ] 若存在边,我们都会将值初始化为 i。因为我们之前说了在关系矩阵当中 [ i, j ] 就代表从 i 到 j 的路径嘛,那最开始大家的前驱节点肯定都是 i 啦。

之后在每一轮更新时,若我们发现了 i → k → j 为最短路径,此时我们就将 [ i, j ] 的值更新为 k 即可。之后我们需要寻找两点的最短路径直接可以用前驱矩阵就可以得到了。

赞(0)
未经允许不得转载:飞天狒狒 » Floyd-Warshall算法详解

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址