作者almaplty (葉瘋)
看板Grad-ProbAsk
標題[理工] Floyd演算法 與負環路
時間Sat Sep 12 00:27:28 2015
http://imgur.com/SMA6n6t
請問圖中 為什麼他說 a到z的距離 是負無限
用floyd演算法 求出最短距離是4 是不對的
我直接看是 a到z 可以抵達阿 距離也的確是4
還是我有什麼不知道的盲點 謝謝
外標題錯字不知道怎麼改 抱歉
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.232.12.2
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1441988850.A.DDE.html
※ 編輯: almaplty (36.232.12.2), 09/12/2015 00:28:00
※ 編輯: almaplty (36.232.12.2), 09/12/2015 00:28:43
推 goldflower: 因為你一把會形成負cycle的點納入時 實際上成本最低 09/12 01:08
→ goldflower: 的path一定會無限繞那個負cycle走 09/12 01:08
→ goldflower: 因為你每繞一次bcdb 距離都會降低 09/12 01:09
→ goldflower: 反正只要記得負cycle無演算法可解就好 09/12 01:10
推 FRAXIS: 負cycle不是無解 而是你要先定義清楚輸出是什麼.. 09/12 01:21
推 goldflower: 呃 我的無解的意思當然不是那個無解XD 09/12 01:30
喔喔 對齁 會一直繞cycle 懂了 感謝!!!
※ 編輯: almaplty (36.232.12.2), 09/12/2015 03:28:05