※ 引述《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)
這兩個演算法步驟幾乎一模一樣,
都是逐次將一個點加入到目前的最短路徑樹/最小花費生成樹當中,
直到全部的點都是樹上的點為止。
唯一的差異是:
建立最短路徑樹每次加入的點都是離起點最近的點,
而建立最小花費生成樹每次加入的點都是離目前的樹最近的點。