[理工] 演算法 Floyd-Warshall中的 Pi矩陣

看板Grad-ProbAsk作者 (汪狗)時間10年前 (2014/02/09 12:28), 編輯推噓0(0推 0噓 9→)
留言9則, 2人參與, 最新討論串1/1
http://ppt.cc/O5CL http://ppt.cc/FpR9 http://ppt.cc/KnP0 http://ppt.cc/ywuf http://ppt.cc/Tk1j http://ppt.cc/wsHI http://ppt.cc/T9Bo 這幾張圖是在說用floyd warshall找出ALL pairs shortest path problem 我的疑問是 D(3)到 D(4) 的pi矩陣(2,5) (3,5)這兩點為什麼是從 2→1呢? 還有(5,2) 為什麼是從NIL→3呢? D(4)代表的意思是path中經過 4th 的意思嗎 而pi(4)是記錄前一個點的內容 那為什麼更動的那些點不是 4 呢? D(4) 到 D(5)也是相同疑問 麻煩各位幫忙解答 感謝: ) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.242.59.194
→
02/09 13:12, , 1F
看code就知道了 只要D中元素有刷新PI就會變 也就是
02/09 13:12, 1F
→
02/09 13:12, , 2F
if Dk-1[i,j]>Dk-1[i,k]+Dk-1[k,j] then PIk[i,j]=
02/09 13:12, 2F
→
02/09 13:13, , 3F
PIk-1[k,j] else PIk[i,j]=PIk-1[i,j]
02/09 13:13, 3F
→
02/09 13:14, , 4F
舉例k=4 PI4(2,5)=PI3(4,5)=1 也就是為什麼2變1
02/09 13:14, 4F
→
02/09 13:33, , 5F
還有Dk不一定經過k若經過變小才會經過 詳細打一下過程
02/09 13:33, 5F
→
02/09 13:34, , 6F
D3[2,5]本來2-5=7最小 PI3[2,5]=2 因為5點前一個是2 但
02/09 13:34, 6F
→
02/09 13:34, , 7F
D4[2,5]變成2-4-1-5=-1才是最小D刷新了 5點前一個點是1
02/09 13:34, 7F
→
02/09 13:35, , 8F
所以PI4=[2,5]=1
02/09 13:35, 8F
→
02/09 14:52, , 9F
瞭解了 感謝ki大大的講解: )
02/09 14:52, 9F
‣ 更多 DOGDOGXD 的文章
文章代碼(AID): #1IzmFoI2 (Grad-ProbAsk)