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

Re: [問題] prim's vs dijkstra

看板Prob_Solve (計算數學 Problem Solving)作者oohay (五黑)時間17年前 (2008/02/17 20:43)推噓2(2推 0噓 8→)

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

Dijkstra在1959年刊登在Numerische Mathematik 1, 269-271的最短路徑算法, 題為 A Note on Two Problems in Connexion with Graphs 與前幾篇文章所提的似乎有些出入. 或許是原典與後續改善者之間的差別吧. Dijkstra的方法是: 要找到圖中P-Q最短路徑,則需持續運用同樣的算法處理P-R最短路徑,R是落在 P-Q最短路徑上的一點. 想一想,若R落在P-Q最短路徑上,則P-R也須是最短路徑, 找到P-Q最短路徑的知識,隱含了找到P-R最短路徑的知識. 方法如下,先將圖分為六群: A 在此的節點都已經知道從P到該點的最短路徑長度. B 在此的節點都未決定最短路徑,卻是下一個可以被選入A的選項 C 其他點 I 在此的邊落在P到達A中任一點的最短路徑上. II 在此的邊是下一個可以被選入I的選項,每條邊都連接到B中某一點. III 其他邊算法: 1. 選取下一個點: "Consider all branches r connecting the node just transferred to set A with nodes R in sets B or C." 如果R在B中,就看看r能不能增加P-R最短路徑. 如果可以,且短於之前找到另一個 P-R',就以目前的R為選中者. 如果R在C中,就把R移到B,把位於III相關的邊移到II. 2. 決定最短路徑P-R: 前一步既然選出了候選者,就把選中者R從B移到A,把位於II相關的最短邊移到I. 做完之後看看Q是否加入了A,如果是就可以結束,且P-Q最短路徑已決定了. 以下是我的操作過程: (P為v1,Q為v9,L(x)是從出發點v1到達x的最短路徑) e1 v1 v2 6 初始決定 L(v1)=0 e2 v1 v3 3 e3 v1 v4 9 第三輪決定 L(v3)=3 e4 v2 v5 8 e5 v2 v8 5 e6 v3 v6 2 第六輪決定 L(v6)=5 e7 v4 v5 9 第七輪決定 L(v7)=8 e8 v6 v7 3 e9 v6 v9 8 e10 v7 v9 2 e11 v8 v9 2 第一輪二輪三輪第四輪第五輪第六輪第七輪 A v1 |v1 |v1,v3|v1,v3 |v1,v3,v6 |v1,v3,v6 |v1,v3,v6,v7 B |v2-4 |v2,v4|v2,v4,v6 |v2,v4 |v2,v4,v7,v9|v2,v4,v9 C v2-9 |v5-9 |v5-9 |v5,v7-9 |v5,v7-9 |v5,v8 |v5,v8 I | |e2 |e2 |e2,e6 |e2,e6 |e2,e6,e8 II |e1-3 |e1,e3|e1,e3,e6 |e1,e3 |e1,e3,e8-9 |e1,e3,e9 III e1-11|e4-11|e4-11|e2,e4-5,e7-11|e2,e4-5,e7-11|e2,e4-5,e7 |e2,e4-5,e7 第八輪沒有畫出來,如果寫出來應該是v9移到A,達成結束條件. 在這練習過程我感到一些疑問,Dijkstra方法提出第一步的第一句話說: "just transferred to set A" 照此做下來是greedy方式,但一般我們需要的是dynamic programming方式, 因為,雖然第七輪已經不考慮v2了,但v1-v2長度為6,小於L(v7),則應該先把v2加進來, 不過v2加進來之後反而使產生的P-Q最短路徑看起來像一棵樹,其中有些支節並不是最短路徑. 隨意竄改可能使方法其不一致. 在此討論謹僅以Dijkstra原論文為主題. 其他書籍所提的方法,日後再討論比較. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.160.108.251 ※ 編輯: oohay 來自: 218.160.108.251 (02/17 20:46) ※ 編輯: oohay 來自: 218.160.108.251 (02/17 20:47)