Floyd-Warshall 算法

Floyd-Warshall 算法


算法 动态规划

Floyd-Warshall 算法使用一种不同的动态规划公式来解决所有结点对最短路径问题,运行时间为 Θ(V3)\Theta(|V|^3),图上可以存在负权重的边,但是不存在负权重的环。本篇将按照动态规划的过程阐述 Floyd 算法,并且拓展如何利用 Floyd 算法找出有向图的传递闭包。

全源最短路径

Floyd 算法考虑的是一条最短路径上的中间结点

中间结点:简单路径 p=<v1,v2,,vl>p=<v_1,v_2,\cdots,v_l> 上的中间结点指的是路径 pp 上除了 v1v_1vlv_l 之外的任意结点,也就是集合 {v2,v3,vl1}\{v_2,v_3\cdots,v_{l-1}\} 中的结点。

假定图 GG 的所有结点为 V={1,2,,n}V=\{1,2,\cdots,n\},考虑其中一个子集 {1,2,,k}\{1,2,\cdots,k\},对于任意结点对 i,jVi,j\in V,考虑从 iijj 的所有中间结点均取自集合 {1,2,,k}\{1,2,\cdots,k\} 的那些路径,并设 pp 为其中权重最小的路径(pp 是简单路径)。我们分别考虑结点 kk 是否是路径 pp 上的一个中间结点的情况。

  • 如果 kk 不是 pp 上的中间结点,则 pp 上所有中间结点都属于集合 {1,2,,k1}\{1,2,\cdots, k-1\}。因此,从 iijj 且中间结点均取自 {1,2,,k1}\{1,2,\cdots,k-1\} 的一条最短路径也同时是从 iijj 且中间结点均取自 {1,2,,k}\{1,2,\cdots,k\} 的一条最短路径。
  • 如果结点 kk 是路径 pp 上的中间结点,则将路径 pp 分解成 p1:ikp_1:i\to kp2:kjp_2: k\to j。可得 p1p_1 是从结点 ii 到结点 kk 的,中间结点全部取自集合 {1,2,,k1}\{1,2,\cdots, k-1\} 的一条最短路径(因为 kk 是末尾结点)。类似的,p2p_2 是从结点 kk 到结点 jj 的,中间结点全部取自集合 {1,2,,k1}\{1,2,\cdots, k-1\} 的一条最短路径。

下图很好的展示了两种不同情况。 FWDP

我们假设 dij(k)d_{ij}^{(k)} 是从结点 ii 到结点 jj 的所有中间结点全部取自 {1,2,,k}\{1,2,\cdots,k\} 的最短路径权重。k=0k=0 时路径只由一条边构成。根据如上定义,我们可以递归定义:

DP

此定义下,矩阵 D(n)=(dij(n))D^{(n)}=(d_{ij}^{(n)}) 就是我们想要的最终答案,因为所有结点都在 1~n 中。

我们可以自底向上计算最短路径权重,算法输入为 n×nn\times n 的矩阵 WW,返回最短路径权重矩阵 D(n)D^{(n)}。算法伪代码如下:

FW

该算法包含三层 for 循环,运行时间为 Θ(n3)\Theta(n^3)

有向图的传递闭包

传递闭包

给定有向图 G=(V,E)G=(V,E),结点集合为 V={1,2,,n}V=\{1,2,\cdots,n\},我们希望判断所有结点对之间是否包含一条 iji\to j 的路径。我们定义图 GG 的传递闭包为图 G=(V,E)G'=(V,E'),其中 E={(i,j)}E'=\{(i,j)\},如果 G 中包含从 iijj 的路径。

思路

如果图 GG 中存在一条从结点 iijj 的所有中间结点都取自集合 {1,2,,k}\{1,2,\cdots,k\} 的路径,则 tij(n)=1t_{ij}^{(n)}=1,否则 tij(n)=0t_{ij}^{(n)}=0。我们构建传递闭包的方法为:将边 (i,j)(i,j) 置于集合 EE' 当且仅当 tij(n)=1t_{ij}^{(n)}=1,递归定义如下:

FW tij(k)=tij(k1)(tik(k1)tkj(k1))k1t_{ij}^{(k)}=t_{ij}^{(k-1)}\vee(t_{ik}^{(k-1)}\land t_{kj}^{(k-1)})\quad\quad k\geq 1

我们同样使用递增的次序计算矩阵 T(k)=(tij(k))T^{(k)}=(t_{ij}^{(k)})

FW

此算法的时间复杂度仍然是 Θ(n3)\Theta(n^3)

© 2024 Hotel