※ 引述《yueimasaka2 (垂哥)》之铭言： : 看了原文书上对Warshall Algorithm的解释 还是不太懂他的意思, : 只知道这是用来算最短距离的 : 下面有练习题 : Find the matrices W0 W1 W2 W3 and W4 : The matrix W4 is the transtive closure of R : W0 = (1,4) (2,1) (2,3) (3,1) (3,4) (4,3) : ANS w1 = (1,4) (2,1) (2,3) (2,4) (3,1) (3,4) (4,3) : w2 = w1 : w3 = (1,4) (2,1) (2,3) (2,4) (3,1) (3,4) (4,1) (4,3) (4,4) : w4 = (1,4) (2,1) (2,3) (2,4) (3,1) (3,3) (3,4) (4,1) (4,3) (4,4) : (原图片是Matrix 抱歉小弟不会用PTT画图) : 可以请高手大大用这题来解释一下他是怎麽算出来的吗? : 感激不尽! ================================================================ Procedure FloydWarshall() for k := 1 to n for i := 1 to n for j := 1 to n dis[i][j] := min( dis[i][j] , dis[i][k]+dis[k][j] ); ================================================================ 以上为FloydWarshall的虚拟码 而你的题目所用到的是Floyd-Warshall Algorithm的简化形式， 单纯判断 (i,j) 是否相连 W0: 　┌─┬─┬─┬─┬─┐ 　│＼│１│２│３│４│ k = 1 ，现在考虑还不相连的Case (i,j)， 　├─┼─┼─┼─┼─┤ 　│１│　│　│　│Ｏ│ 如果 (i,k) == Ｏ 且 (k,j) == Ｏ 则 (i,j) := Ｏ 　├─┼─┼─┼─┼─┤ 　│２│Ｏ│　│Ｏ│　│ Ex: (2,1) == Ｏ 且 (1,4) == Ｏ -> (2,4) := Ｏ 　├─┼─┼─┼─┼─┤ 　│３│Ｏ│　│　│Ｏ│ 满足条件的(i,j)： { (2,4) } 　├─┼─┼─┼─┼─┤ 　│４│　│　│Ｏ│　│ 　└─┴─┴─┴─┴─┘ W1: ※红色代表新增的路径 ┌─┬─┬─┬─┬─┐ 　│＼│１│２│３│４│ k = 2 ，一样考虑还不相连的Case 　├─┼─┼─┼─┼─┤ 　│１│ │　│　│Ｏ│ if ((i,k) == Ｏ and (k,j) == Ｏ) then (i,j) := Ｏ 　├─┼─┼─┼─┼─┤ 　│２│Ｏ│ │Ｏ│Ｏ│ 满足条件的(i,j)：ψ 　├─┼─┼─┼─┼─┤ 　│３│Ｏ│　│ │Ｏ│ 　├─┼─┼─┼─┼─┤ 　│４│　│　│Ｏ│ │ 　└─┴─┴─┴─┴─┘ W2: ┌─┬─┬─┬─┬─┐ 　│＼│１│２│３│４│ k = 3 　├─┼─┼─┼─┼─┤ 　│１│ │　│　│Ｏ│ 满足条件的(i,j): { (4,1) , (4,4) } 　├─┼─┼─┼─┼─┤ 　│２│Ｏ│ │Ｏ│Ｏ│ 　├─┼─┼─┼─┼─┤ 　│３│Ｏ│　│ │Ｏ│ 　├─┼─┼─┼─┼─┤ 　│４│　│　│Ｏ│ │ 　└─┴─┴─┴─┴─┘ W3: ┌─┬─┬─┬─┬─┐ 　│＼│１│２│３│４│ k = 4 　├─┼─┼─┼─┼─┤ 　│１│　│　│　│Ｏ│ 满足条件的(i,j): { (3,3) } 　├─┼─┼─┼─┼─┤ 　│２│Ｏ│　│Ｏ│Ｏ│ 　├─┼─┼─┼─┼─┤ 　│３│Ｏ│　│　│Ｏ│ 　├─┼─┼─┼─┼─┤ 　│４│Ｏ│　│Ｏ│Ｏ│ 　└─┴─┴─┴─┴─┘ W4 ┌─┬─┬─┬─┬─┐ 　│＼│１│２│３│４│ Done~ 　├─┼─┼─┼─┼─┤ 　│１│　│　│　│Ｏ│ 　├─┼─┼─┼─┼─┤ 　│２│Ｏ│　│Ｏ│Ｏ│ 　├─┼─┼─┼─┼─┤ 　│３│Ｏ│　│Ｏ│Ｏ│ 　├─┼─┼─┼─┼─┤ 　│４│Ｏ│　│Ｏ│Ｏ│ 　└─┴─┴─┴─┴─┘ ================================================= Floyd-Warshall Algorithm其实是用到DP的概念， 假设 D[k][i][j]代表的是，由 i 走到 j ， 路途中只经过编号不大於k的点，所能得到的最小值 => D[k][i][j] = min( D[k-1][i][j] , D[k-1][i][k]+D[k-1][k][j] ) 如此一来，当D[][][]全部被填完之後，D[n][i][j]存的就是 i 到 j 的最短路径长 为什麽呢？ 假设从i走到j必须要经过某些点，这些点中最大的编号为 k_m 也就是 D[n][i][j] = D[n-1][i][j] = D[n-2][i][j] = ... = D[k_m][i][j] 且 D[k_m][i][j] = D[n][i][k_m] + D[n][k_m][j] 现在考虑 i 到 k_m 的距离 i 到 k_m 的最短路径一定不需要经过 编号大於等於 k_m 的点 於是就有： D[n][i][k_m] = D[n-1][i][k_m] = ... = D[k_m-1][i][k_m] 同理，故 D[k_m][i][j] = D[k_m-1][i][k_m] + D[k_m-1][k_m][j] 以上是说明法， 如果要证明的话可以用归纳法， 假设D[k][i][j] 对所有的 (i,j) 都存有 经过编号不大於k的点所能产生的最短路径 再证明 D[k+1][i][j] 也有同样的性质 而初始条件是: D[0][i][j] 代表不经过任何点，直接从i走到j的路径长 我想应该就满完整了 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.228.153.124