※ 引述《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)