作者DeathSimon (死西门)
站内Prob_Solve
标题Re: [问题] prim's vs dijkstra
时间Fri Feb 8 17:07:01 2008
※ 引述《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
1F：推 fantasywater:非常清楚 我懂了 感谢回答 新年快乐︿︿ 02/08 17:14