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

Re: [問題] prim's vs dijkstra

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

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

※ 引述《DeathSimon (死西門)》之銘言： : ※ 引述《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一樣 : 希望這樣有比較清楚解答你的問題^^ 我認為這個解釋不對勁,不對勁是在Dijkstra's部份. 若說尋找從A到達各點的最短路徑,答案找出一個最短路徑樹的確沒問題. (最短路徑樹是擴張樹,但不見得是最小擴張樹.) 但Dijkstra所提的方法不是算ㄧ棵樹. (I'm sorry that I cannot type chinese suddenly while writing this post.) According to Dijkstra's paper in 1959, two problems were solved, the former is so-called minimal spanning tree, and the later shortest path problem. In the Problem 2, it was defined to find a path with minimal total length between two given nodes P and Q, ad the algorithm was depicted that solving steps ends when the destining Q is added to the set of "nodes for which the path of minimal length from P is known". The invariant condition of the loop is what Dijkstra's algorithm differs from Prim's algorithm. Thus, one or more shortest paths connecting from P to Q can be chose. but not all shortest paths from P to the remaining nodes. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.70.212 ※ 編輯: oohay 來自: 61.231.70.212 (02/13 16:26)