作者DJWS (...)
看板Prob_Solve
标题Re: [问题] prim's vs dijkstra
时间Sun Feb 10 20:36:14 2008
这两个演算法步骤几乎一模一样，
都是逐次将一个点加入到目前的最短路径树/最小花费生成树当中，
直到全部的点都是树上的点为止。
唯一的差异是：
建立最短路径树每次加入的点都是离起点最近的点，
而建立最小花费生成树每次加入的点都是离目前的树最近的点。
※ 引述《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)