[理工] Floyd-Warshall矩陣運算問題

看板Grad-ProbAsk作者時間6年前 (2017/10/27 14:35), 6年前編輯推噓6(6推 0噓 2→)
留言8則, 3人參與, 6年前最新討論串1/1
想請問一下，使用Floyd-Warshall 求最短路徑裡面矩陣運算的問題， https://i.imgur.com/L12X4Rd.jpg
在例題中， 為何矩陣A^k中的第k行、第k列不需要做運算? 例如矩陣A^2中的頂點2->頂點3路徑， 除了2->3之外，不是還有2->1->3這種可能嗎? 為何能直接斷定2->3路徑長一定比2->1->3短? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.40.159.56 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1509086120.A.FAC.html ※ 編輯: elephanting (114.40.159.56), 10/27/2017 14:35:54
推
10/27 15:20, 6年前 , 1F
你知道floyd-warshall的原理嗎
10/27 15:20, 1F
→
10/27 15:21, 6年前 , 2F
他第k輪算出的是 "除了起終點只通過小於k的點"
10/27 15:21, 2F
推
10/27 15:23, 6年前 , 3F
所以以你的例子 2->1->3的cost在上一輪就算出來了
10/27 15:23, 3F
推
10/27 15:27, 6年前 , 4F
因為你 2->3路徑長跟2->1->3在A^1中考慮過了
10/27 15:27, 4F
推
10/27 20:45, 6年前 , 5F
Ak 意義是經過點1到k的最小路徑不是嗎
10/27 20:45, 5F
推
10/27 20:48, 6年前 , 6F
某一點vi走到vk的最短路徑途中一定不會有vk的呀所以
10/27 20:48, 6F
→
10/27 20:48, 6年前 , 7F
答案會一樣
10/27 20:48, 7F
推
10/27 20:50, 6年前 , 8F
Ak的意義是除了起終點中間經過的點要是1到k之間
10/27 20:50, 8F
‣ 更多 elephanting 的文章
文章代碼(AID): #1PyjEe-i (Grad-ProbAsk)