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

Re: [問題] Johnson跟reweighting

看板Prob_Solve (計算數學 Problem Solving)作者blackZ2 (ＢＢ)時間13年前 (2011/09/07 01:32)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串2/3 (看更多)

先說很可能會講錯,這是自己看書慢慢理解的,並不掛保證 p.s 書是補習班講義洪捷的演算法-名校攻略秘笈 p.4-55 範例7 ※ 引述《mqazz1 (無法顯示)》之銘言： Johnson的演算法那部分有這個圖 http://ppt.cc/1(V; 最左邊的那個node是新加入的node 然後有一些問題 1. 如何及時發現，原graph有negative cycle ? 如果我回答，跑n次Bellman-Ford，發現有新的node被relaxtion，這樣算及時嗎時間複雜度為 O(|V|) , 應該可以吧, 這題我無法明確回答你, 我也不知道及時的定義 2. 上面那個圖，新加的一node造成新的graph，是否會產生新的negative cycle ? negative cycle 定義為整個 cycle 路徑總長為負值而新加的點都指向其他點, 不要說負值了, 連cycle都沒有 3. 上面那個圖，新加的node作用是在做甚麼? 不加可以嗎? 演算法是天才想的,天才說要加,就得加... Johnson's algo 的步驟如下 (節錄算法-名校攻略秘笈 p.4-56) 1. 加一個點 s，到其他點均有 edge，其上 weight 為 0。 (s均指向其他點,所以一定不會因為加s與其邊產生cycle) 2.執行Bellman-Ford演算法，若無負cycle，則記錄每一點的h(v)為自s到v之shortest path 長。 3.對每一個edge做reweight如下： w'(u,v) = w(u,v)+h(u)-h(v)。 4.對每一個點執行Dijkstra's algotithm。其實Johnson's algo重點就是在於reweight 讓每個edge為正值，這樣就絕對不會有negative cycle 而加node只是有個基準點吧 p.s 如果你有書,你可以參考 p.4-57 ex9, 用來解不等式, 感覺蠻方便的 -- 其實我是來賺P幣的 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.66.93