Re: [問題] prim's vs dijkstra
看板Prob_Solve (計算數學 Problem Solving)作者DeathSimon (死西門)時間17年前 (2008/02/08 17:07)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/8 (看更多)
※ 引述《fantasywater (狂想)》之銘言：
: 請問一下
: 這兩個演算法差別在哪裡?
Prim是求MST
Dij是求single source shortest path
: 會問這個問題是因為兩個演算法的步驟好像一樣
: 而且似乎都會得到一棵相同的minimum spannig tree
直接舉例:
10 20
A------B-------C
| | 2
---------------D
30
Prim會得到 而以A為起始點的dij會得到: AB=10, AC=30, AD=30
化成圖表示成這樣:
10 20 10 20
A------B------C A-----B-----C
| 2 |
D ------------D
30
不過如果dij取C為起點的話，結果就會跟Prim的一樣是MST
你會得到相同MST可能是只是因為那個起點用Dij得到的結果化成圖跟Prim一樣
希望這樣有比較清楚解答你的問題^^
--
有講錯的地方還請多多指教
祝大家新年快樂:)
--
也或許，
我在承認失敗的背後，
還在等待著什麼？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.137.247
推
02/08 17:14, , 1F
02/08 17:14, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
