PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] johnson algorithm

看板Prob_Solve (計算數學 Problem Solving)作者 (straw man)時間10年前 (2014/12/25 00:03), 10年前編輯推噓2(2推 0噓 4→)
留言6則, 2人參與, 最新討論串1/1
請問一下 當執行johnson algo時 會先跑一個weight function 來確保沒有負的weight出現 如果圖形中原來存在一個0-weight cycle時 當reweight完之後 該cycle中的每個邊weight均會是0 請問為什麼會有這種情況?? -- -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.214.127 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1419437005.A.1C6.html ※ 編輯: jb679123 (140.123.214.127), 12/25/2014 00:03:40
推
12/25 03:47, , 1F
容易知道 reweight 後任一 cycle 的總 cost 不變
12/25 03:47, 1F
→
12/25 03:49, , 2F
且 reweight 後任一邊皆非負, 故零圈上的邊都會變成零
12/25 03:49, 2F
推
12/25 09:32, , 3F
0-weight cycle上面每一個點 最短路徑長度通通一樣長
12/25 09:32, 3F
→
12/25 09:34, , 4F
reweight的式子是 w(a.b) + h(a) - h(b) 其中h(a) h(b)一樣
12/25 09:34, 4F
→
12/25 09:35, , 5F
調整之後 0-weight cycle上面每一個邊 weight 都保持一樣
12/25 09:35, 5F
→
12/25 09:35, , 6F
一樣都是 0
12/25 09:35, 6F
感謝D大和L大的解說 ※ 編輯: jb679123 (140.123.103.109), 12/25/2014 09:46:56
‣ 更多 jb679123 的文章
文章代碼(AID): #1KckFD76 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jb679123 的文章
文章代碼(AID): #1KckFD76 (Prob_Solve)