作者oohay (五黑)
看板Prob_Solve
標題Re: [問題] prim's vs dijkstra
時間Sun Feb 17 20:43:47 2008
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)
推 smallworld:其實如果有作業研究的課本 裡面就把這方法 02/17 23:14
→ smallworld:的筆算過程 很清楚的走一次 可去找Lieberman的課本 02/17 23:14
→ smallworld:來參考 02/17 23:18
→ oohay:這講法很混淆;並不是每本OR都如此談Dijkstra,也不是每個談 02/18 00:00
→ oohay:的都跟著這方法 02/18 00:01
→ oohay:目前看過好幾版本的DA,很混淆,於是想逐項練習釐清差異. 02/18 00:06
→ oohay:Lieberman的OR我會去找來看,謝謝指教. 02/18 00:08
→ oohay:已經讀過Lieberman的Intro. OR,講的的確是1959 Dijkstra's 02/22 23:15
推 smallworld:老實說 我讀過OR之後 研究所上演算法真的很輕鬆... 02/23 19:46
→ oohay:研究所的演算法比不上大學演算法,前者聽不懂也不打緊 02/23 22:57