1. PTT
  2. Prob_Solve

[问题] johnson algorithm

楼主: jb679123 (straw man)   2014-12-25 00:03:21
请问一下
当执行johnson algo时
会先跑一个weight function
来确保没有负的weight出现
如果图形中原来存在一个0-weight cycle时
当reweight完之后
该cycle中的每个边weight均会是0
请问为什么会有这种情况??
作者: LPH66 (-6.2598534e+18f)   2014-12-25 03:47:00
容易知道 reweight 后任一 cycle 的总 cost 不变且 reweight 后任一边皆非负, 故零圈上的边都会变成零
作者: DJWS (...)   2014-12-25 09:32:00
0-weight cycle上面每一个点 最短路径长度通通一样长reweight的式子是 w(a.b) + h(a) - h(b) 其中h(a) h(b)一样调整之后 0-weight cycle上面每一个边 weight 都保持一样一样都是 0
继续阅读
[问题] 类似背包问题cutekidRe: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)LPH66Re: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)flereRe: [问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)LPH66[问题] 记忆游戏 (更新暴力法解随机翻的情况, 求正常翻的机率)GenialPP[问题] 以已知数反推其位于数列中第几项unsh[问题] 一串数字中找到相同的两个数penknifelee[问题] beam searchcsam11000[讨论] perfect hashingsandy4444Re: [问题] Missing NumbersFRAXIS

Links booklink

Contact Us: admin [ a t ] ucptt.com