※ 引述《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