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