作者jb679123 (straw man)
看板Prob_Solve
標題[問題] johnson algorithm
時間Thu Dec 25 00:03:21 2014
請問一下
當執行johnson algo時
會先跑一個weight function
來確保沒有負的weight出現
如果圖形中原來存在一個0-weight cycle時
當reweight完之後
該cycle中的每個邊weight均會是0
請問為什麼會有這種情況??
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.214.127
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1419437005.A.1C6.html
※ 編輯: jb679123 (140.123.214.127), 12/25/2014 00:03:40
1F：推 LPH66: 容易知道 reweight 後任一 cycle 的總 cost 不變 12/25 03:47
2F：→ LPH66: 且 reweight 後任一邊皆非負, 故零圈上的邊都會變成零 12/25 03:49
3F：推 DJWS: 0-weight cycle上面每一個點 最短路徑長度通通一樣長 12/25 09:32
4F：→ DJWS: reweight的式子是 w(a.b) + h(a) - h(b) 其中h(a) h(b)一樣 12/25 09:34
5F：→ DJWS: 調整之後 0-weight cycle上面每一個邊 weight 都保持一樣 12/25 09:35
6F：→ DJWS: 一樣都是 0 12/25 09:35
感謝D大和L大的解說
※ 編輯: jb679123 (140.123.103.109), 12/25/2014 09:46:56