Floyd-Warshall 算法 Nov 11, 2020 算法 动态规划
Floyd-Warshall 算法使用一种不同的动态规划公式来解决所有结点对最短路径问题,运行时间为 Θ ( ∣ V ∣ 3 ) \Theta(|V|^3) Θ ( ∣ V ∣ 3 ) ,图上可以存在负权重的边,但是不存在负权重的环。本篇将按照动态规划的过程阐述 Floyd 算法,并且拓展如何利用 Floyd 算法找出有向图的传递闭包。
全源最短路径
Floyd 算法考虑的是一条最短路径上的中间结点 。
中间结点 :简单路径 p = < v 1 , v 2 , ⋯ , v l > p=<v_1,v_2,\cdots,v_l> p =< v 1 , v 2 , ⋯ , v l > 上的中间结点指的是路径 p p p 上除了 v 1 v_1 v 1 和 v l v_l v l 之外的任意结点,也就是集合 { v 2 , v 3 ⋯ , v l − 1 } \{v_2,v_3\cdots,v_{l-1}\} { v 2 , v 3 ⋯ , v l − 1 } 中的结点。
假定图 G G G 的所有结点为 V = { 1 , 2 , ⋯ , n } V=\{1,2,\cdots,n\} V = { 1 , 2 , ⋯ , n } ,考虑其中一个子集 { 1 , 2 , ⋯ , k } \{1,2,\cdots,k\} { 1 , 2 , ⋯ , k } ,对于任意结点对 i , j ∈ V i,j\in V i , j ∈ V ,考虑从 i i i 到 j j j 的所有中间结点均取自集合 { 1 , 2 , ⋯ , k } \{1,2,\cdots,k\} { 1 , 2 , ⋯ , k } 的那些路径,并设 p p p 为其中权重最小的路径(p p p 是简单路径)。我们分别考虑结点 k k k 是否是路径 p p p 上的一个中间结点的情况。
如果 k k k 不是 p p p 上的中间结点,则 p p p 上所有中间结点都属于集合 { 1 , 2 , ⋯ , k − 1 } \{1,2,\cdots, k-1\} { 1 , 2 , ⋯ , k − 1 } 。因此,从 i i i 到 j j j 且中间结点均取自 { 1 , 2 , ⋯ , k − 1 } \{1,2,\cdots,k-1\} { 1 , 2 , ⋯ , k − 1 } 的一条最短路径也同时是从 i i i 到 j j j 且中间结点均取自 { 1 , 2 , ⋯ , k } \{1,2,\cdots,k\} { 1 , 2 , ⋯ , k } 的一条最短路径。
如果结点 k k k 是路径 p p p 上的中间结点,则将路径 p p p 分解成 p 1 : i → k p_1:i\to k p 1 : i → k 和 p 2 : k → j p_2: k\to j p 2 : k → j 。可得 p 1 p_1 p 1 是从结点 i i i 到结点 k k k 的,中间结点全部取自集合 { 1 , 2 , ⋯ , k − 1 } \{1,2,\cdots, k-1\} { 1 , 2 , ⋯ , k − 1 } 的一条最短路径(因为 k k k 是末尾结点)。类似的,p 2 p_2 p 2 是从结点 k k k 到结点 j j j 的,中间结点全部取自集合 { 1 , 2 , ⋯ , k − 1 } \{1,2,\cdots, k-1\} { 1 , 2 , ⋯ , k − 1 } 的一条最短路径。
下图很好的展示了两种不同情况。
我们假设 d i j ( k ) d_{ij}^{(k)} d ij ( k ) 是从结点 i i i 到结点 j j j 的所有中间结点全部取自 { 1 , 2 , ⋯ , k } \{1,2,\cdots,k\} { 1 , 2 , ⋯ , k } 的最短路径权重。k = 0 k=0 k = 0 时路径只由一条边构成。根据如上定义,我们可以递归定义:
此定义下,矩阵 D ( n ) = ( d i j ( n ) ) D^{(n)}=(d_{ij}^{(n)}) D ( n ) = ( d ij ( n ) ) 就是我们想要的最终答案,因为所有结点都在 1~n 中。
我们可以自底向上计算最短路径权重,算法输入为 n × n n\times n n × n 的矩阵 W W W ,返回最短路径权重矩阵 D ( n ) D^{(n)} D ( n ) 。算法伪代码如下:
该算法包含三层 for 循环,运行时间为 Θ ( n 3 ) \Theta(n^3) Θ ( n 3 ) 。
有向图的传递闭包
传递闭包
给定有向图 G = ( V , E ) G=(V,E) G = ( V , E ) ,结点集合为 V = { 1 , 2 , ⋯ , n } V=\{1,2,\cdots,n\} V = { 1 , 2 , ⋯ , n } ,我们希望判断所有结点对之间是否包含一条 i → j i\to j i → j 的路径。我们定义图 G G G 的传递闭包为图 G ′ = ( V , E ′ ) G'=(V,E') G ′ = ( V , E ′ ) ,其中 E ′ = { ( i , j ) } E'=\{(i,j)\} E ′ = {( i , j )} ,如果 G 中包含从 i i i 到 j j j 的路径。
思路
如果图 G G G 中存在一条从结点 i i i 到 j j j 的所有中间结点都取自集合 { 1 , 2 , ⋯ , k } \{1,2,\cdots,k\} { 1 , 2 , ⋯ , k } 的路径,则 t i j ( n ) = 1 t_{ij}^{(n)}=1 t ij ( n ) = 1 ,否则 t i j ( n ) = 0 t_{ij}^{(n)}=0 t ij ( n ) = 0 。我们构建传递闭包的方法为:将边 ( i , j ) (i,j) ( i , j ) 置于集合 E ′ E' E ′ 当且仅当 t i j ( n ) = 1 t_{ij}^{(n)}=1 t ij ( n ) = 1 ,递归定义如下:
t i j ( k ) = t i j ( k − 1 ) ∨ ( t i k ( k − 1 ) ∧ t k j ( k − 1 ) ) k ≥ 1 t_{ij}^{(k)}=t_{ij}^{(k-1)}\vee(t_{ik}^{(k-1)}\land t_{kj}^{(k-1)})\quad\quad k\geq 1 t ij ( k ) = t ij ( k − 1 ) ∨ ( t ik ( k − 1 ) ∧ t kj ( k − 1 ) ) k ≥ 1
我们同样使用递增的次序计算矩阵 T ( k ) = ( t i j ( k ) ) T^{(k)}=(t_{ij}^{(k)}) T ( k ) = ( t ij ( k ) ) 。
此算法的时间复杂度仍然是 Θ ( n 3 ) \Theta(n^3) Θ ( n 3 ) 。