作者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/cn.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