Re: [問題] prim's vs dijkstra
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間17年前 (2008/02/10 20:36)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/8 (看更多)
這兩個演算法步驟幾乎一模一樣，
都是逐次將一個點加入到目前的最短路徑樹/最小花費生成樹當中，
直到全部的點都是樹上的點為止。
唯一的差異是：
建立最短路徑樹每次加入的點都是離起點最近的點，
而建立最小花費生成樹每次加入的點都是離目前的樹最近的點。
※ 引述《seanwu (Blindest)》之銘言：
: ※ 引述《fantasywater (狂想)》之銘言：
: : 請問一下
: : 這兩個演算法差別在哪裡?
: : 會問這個問題是因為兩個演算法的步驟好像一樣
: : 而且似乎都會得到一棵相同的minimum spannig tree
: 求mst的Dijkstra算法
: http://www.badongo.com/file/7708575 (page 37)
: 可是我一直覺得那應該叫prim ..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.130.174
※ 編輯: DJWS 來自: 220.137.130.174 (02/10 20:43)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
