Prim和Dijkstraalgorithm之间的区别？
Dijkstra和Prim的algorithm有什么区别？ 我知道Prim会给MST，但是Dijkstra生成的树也会是MST。 那么究竟有什么区别？
Prim的algorithm为graphics构造了一棵最小生成树 ，它是连接图中所有节点的树，在连接所有节点的所有树中总成本最小。 但是，MST中任意两个节点之间的path长度可能不是原始图中这两个节点之间的最短path。 例如，如果您想以最小的总成本物理连接图中的节点以向其供电，则MST非常有用。 两个节点之间的path长度可能不是最佳的，因为你所关心的只是它们连接的事实。
Dijkstraalgorithm从一些源节点开始构build最短path树 。 最短path树是将图中的所有节点连接回源节点的树，并具有从源节点到图中的任何其他节点的任何path的长度最小化的属性。 例如，如果你想build立一个道路networking，使每个人都能尽可能高效地到达一些重要的地标，这是非常有用的。 但是，最短path树不能保证是最小生成树，构build这样的树的成本可能比MST的成本要大得多。
另一个重要的区别涉及algorithm的工作types。 Prim的algorithm仅适用于无向图，因为MST的概念假定图本质上是无向的。 （对有向图而言，有一种叫做“最小跨越树状”的algorithm，但是find它们的algorithm要复杂得多）。 Dijkstra的algorithm在有向图上可以很好地工作，因为最短path树确实可以被引导。 另外，Dijkstraalgorithm不一定能在包含负边权重的图中产生正确的解 ，而Primalgorithm可以处理这个问题。
希望这可以帮助！
Dijkstraalgorithm不创buildMST，它find最短path。
考虑这个图
5 5 s *-----*-----* t \ / ------- 9
最短path是9，而MST是10的不同“path”。
Prim和Dijkstraalgorithm几乎相同，除了“放松函数”。
在Prim：
MST-PRIM (G, w, r) { for each key ∈ GV u.key = ∞ u.parent = NIL r.key = 0 Q = GV while (Q ≠ ø) u = Extract-Min(Q) for each v ∈ G.Adj[u] if (v ∈ Q) and w(u,v) < v.key v.parent = u v.key = w(u,v) <== relax function, Pay attention here }
在Dijkstra：
Dijkstra (G, w, r) { for each key ∈ GV u.key = ∞ u.parent = NIL r.key = 0 Q = GV while (Q ≠ ø) u = Extract-Min(Q) for each v ∈ G.Adj[u] if (v ∈ Q) and w(u,v) < v.key v.parent = u v.key = w(u,v) + u.key <== relax function, Pay attention here }
唯一的区别是代码的最后一行，这是放松function。 search最小生成树的Prim只关心覆盖所有顶点的所有边的最小值。 所以它看起来像：v.key = w（u，v）Dijkstrasearch最小path长度，所以它关心边缘积累。 所以它看起来像：v.key = w（u，v）+ u.key
Dijkstrafind它的开始节点和其他每个节点之间的最短path。 因此，作为回报，您可以从开始节点获得最小距离树，即可以尽可能高效地到达其他每个节点。
Primsalgorithm为您提供给定graphics的MST，即连接所有节点的树，而所有成本的总和是最小的。
用一个现实的例子来说一个故事：
- Dijkstra希望通过节省旅行时间和燃料来知道到达每个目的地点的最短path。
- Prim想知道如何有效地部署火车轨道系统，即节省材料成本。
直接从Dijkstraalgorithm的维基百科文章：
Dijkstraalgorithm的基础过程与Primalgorithm中使用的贪婪过程相似。 Prim的目的是find连接图中所有节点的最小生成树; Dijkstra只关心两个节点。 Prim's不计算从起始节点到唯一path的path总重量。
基本algorithm之间的主要区别在于其不同的边缘select标准。 通常，它们都使用优先级队列来select下一个节点，但是具有不同的标准来select当前处理节点的相邻节点：Primalgorithm要求下一个相邻节点也必须保持在队列中，而Dijkstraalgorithm不需要：
def dijkstra(g, s): q <- make_priority_queue(VERTEX.distance) for each vertex v in g.vertex: v.distance <- infinite v.predecessor ~> nil q.add(v) s.distance <- 0 while not q.is_empty: u <- q.extract_min() for each adjacent vertex v of u: ... def prim(g, s): q <- make_priority_queue(VERTEX.distance) for each vertex v in g.vertex: v.distance <- infinite v.predecessor ~> nil q.add(v) s.distance <- 0 while not q.is_empty: u <- q.extract_min() for each adjacent vertex v of u: if v in q and weight(u, v) < v.distance:// <-------selection-------- ...
vertex.distance的计算是第二个不同点。
@templatetypedef覆盖了MST和最短path之间的区别。 我已经介绍了另一个algorithm的差异所以通过certificate这两个都可以使用相同的一般algorithm，多个参数作为input来实现：function f(u,v) 。 Prim和Dijkstraalgorithm之间的差别就是你使用的f(u,v) 。
在代码级别上，另一个区别是API。
您使用源顶点s （即Prim.new(s)初始化Prim; s可以是任意的顶点，不pipes是多less，最终结果是最小生成树（MST）的边是相同的。 为了得到MST边缘，我们称之为方法edges() 。
您使用源顶点s （即Dijkstra.new(s)初始化Dijkstra，您希望获得所有其他顶点的最短path/距离。 最终结果是从s到所有其他顶点的最短path/距离; 根据s而不同。 为了得到s到任何顶点的最短path/距离v ，我们分别称为distanceTo(v)和pathTo(v) 。
