推 micklin:推 06/09 23:37
看了原文書上對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畫圖)
可以請高手大大用這題來解釋一下他是怎麼算出來的嗎?
感激不盡!
--
表氏宗親家族聚會
◢██ ◣ ◢███◣◢███◣◢███◣◢███◣◢███◣
██◥◥ 其他人呢? ◢表哥 █◢大表弟█◢二表弟█◢三表弟█◢四表弟█
█ ● ● ◢ ▂ ▂ ▕▂ ▂ ▕▂ ▂ ▕▂ ▂ ▕▂ ▂ ▕
█◥ ︶◢ 還在歐兔相認中 — — ⊙⊙ - - ^ ^ ＊ ＊
◢ ◥◢ ◣ ▋ ▋ ▋ ▋ 皿 ▋
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 70.42.120.240
> -------------------------------------------------------------------------- <
作者: stimim (qqaa) 看板: ask-why
標題: Re: [請益] Warshall algorithm
時間: Mon Jun 8 21:47:00 2009
※ 引述《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