作者elephanting ()
看板Grad-ProbAsk
標題[理工] Floyd-Warshall矩陣運算問題
時間Fri Oct 27 14:35:16 2017
想請問一下，使用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
推 can18: 你知道floyd-warshall的原理嗎 10/27 15:20
→ can18: 他第k輪算出的是 "除了起終點只通過小於k的點" 10/27 15:21
推 can18: 所以以你的例子 2->1->3的cost在上一輪就算出來了 10/27 15:23
推 q1qip123: 因為你 2->3路徑長跟2->1->3在A^1中考慮過了 10/27 15:27
推 TMDTMD2487: Ak 意義是經過點1到k的最小路徑不是嗎 10/27 20:45
推 TMDTMD2487: 某一點vi走到vk的最短路徑途中一定不會有vk的呀所以 10/27 20:48
→ TMDTMD2487: 答案會一樣 10/27 20:48
推 TMDTMD2487: Ak的意義是除了起終點中間經過的點要是1到k之間 10/27 20:50
