是什么Dijkstra的和普里姆的算法之间准确的区别？ 我知道普里姆的将给予MST而是通过Dijkstra算法生成的也将是一个MST树。 那么，什么是准确的区别？
Answer 1:
Prim算法构造一个最小生成树的图，它是连接图中的所有节点，并具有连接所有节点的所有树木中，至少总成本的一棵树。 然而，任何两个节点之间的路径中的MST长度可能不是在原始图表这两个节点之间的最短路径。 MSTS是有用的，例如，如果你想身体的电缆铺设工作节点在图表中以最低的总成本为他们提供电力。 这不要紧，两个节点之间的路径长度可能不是最佳的，因为所有你关心的是，他们连这样的事实。
Dijkstra算法构建了一个最短路径树从某个源节点出发。 的最短路径树的是，图中的背面连接的所有节点到源节点并具有从源节点到图中的任何其他节点的任何路径的长度被最小化的性质的树。 这是有用的，例如，如果你想建立一个路网，使得它尽可能有效地为大家去一些大重要里程碑。 然而，最短路径树是不能保证是最小生成树，并建立了一种树木的成本可能比MST的成本大得多。
另一个重要的区别是什么顾虑类型的图形算法的努力。 Prim算法适用于只无向图，由于MST的概念，假定图是天生无向。 （也有一些是被称为“最小生成树树状”对于有向图，但算法来找到他们要复杂得多）。 Dijkstra算法将工作有向图很好的，因为最短路径树的确可以引导。 此外，Dijkstra算法并不一定产生于含负边权重图的正确的解决方案 ，而Prim算法可以处理这个问题。
希望这可以帮助！
Answer 2:
Dijkstra算法不创建一个MST，它发现的最短路径。
考虑一下这个图
5 5
s *-----*-----* t
\ /
-------
9
的最短路径是9，而MST为10不同的“路径”。
Answer 3:
普里姆和Dijkstra算法几乎相同，除了“放松功能”。
在普里姆：
MST-PRIM (G, w, r) {
for each key ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
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 ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
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
}
唯一的区别是该代码，这是放松函数的最后一行。 古板，其搜索最小生成树，只关心最小的总的边缘覆盖所有的顶点。 所以它看起来像：v.key = W（U，V）的迪杰斯特拉，其搜索最小路径长度，因此它关心的边缘累积。 所以它看起来像：v.key = W（U，V）+ u.key
Answer 4:
Dijkstra算法发现它之间的最短路径就要开始节点和所有其他节点。 因此，在回你从开始节点的最小距离树，即你可以尽可能高效地到达所有其他节点。
普里姆算法让你的MST对于给定的图形，即连接的所有节点，而所有费用的总和最小可能的树。
为了使故事短，一个现实的例子：
- Dijkstra算法希望通过节省旅行时间和燃料，以了解每个目的地的最短路径。
- 普里姆想知道如何有效地部署火车铁路系统，即节省了材料成本。
Answer 5:
直接从Dijkstra算法的维基百科文章：
该underlies Dijkstra算法的过程是类似Prim算法使用的贪婪过程。 普里姆的目的是找到一个最小生成树连接图中的所有节点; Dijkstra算法仅涉及两个节点。 普里姆的不从起始节点，只有个别路径计算路径的总重量。
Answer 6:
基本算法之间的主要区别在于它们的不同边缘的选择标准。 一般情况下，它们都使用优先级队列中选择下一个节点，但有不同的标准来选择当前处理节点的相邻节点：Prim算法要求相邻的下一个节点也必须保持在队列中，而Dijkstra算法并不：
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的计算是第二个不同点。
Answer 7:
第一个区别是，Dijkstra算法解决了克鲁斯卡比和普里姆不同的问题。 迪杰斯特拉解决了最短路径问题（从指定的节点），而采用Kruskal和的Prim发现一个最小代价生成树。 以下是说明我在这个页面写的改进形式：图形算法。
对任意一个图中，生成树是足以提供每对顶点之间恰好一个路径的边的集合。 此限制意味着，不可能有由所选边缘形成的电路。
最小成本生成树是一个具有最小可能的总重量（其中，权重表示成本或距离）。 可能有不止一个这样的树，但普里姆和克鲁斯卡都肯定可以找到其中的一个。
对于一个指定的顶点（表示X），所述最短路径树是一个生成树，使得从X到任何其他顶点的路径是尽可能短（即，具有最小可能的重量计）。
道貌岸然的Dijkstra算法从顶点开始“成长”的树了。 换句话说，他们有一个“本地”的重点; 在每一步中，我们只考虑那些边缘紧邻先前选择的顶点，选择满足我们的需求，最便宜的选择。 同时，采用Kruskal是一个“全球性”算法，这意味着每个边缘（贪婪地）从整个图选择的。 （实际上，可能的Dijkstra被视为具有一些全局方面，如下所述。）
为了找到一个最低成本生成树：
克鲁斯卡（环球法）：在每个步骤中，选择最便宜的边缘的任何地方不违反创造一个生成树的目标。 普里姆（本地方法）：选择一个开始顶点。 在每个连续的步骤，选择连接到不违反创造一个生成树的目标的任何先前选择的顶点最便宜的优势。 要找到最短路径生成树：
迪杰斯特拉：在每一步中，选择连接到这使得从起始顶点（全球方面）尽可能小的总距离的任何先前选择的顶点（本地方面）的边缘，以及不违反创建生成树的目标。
最小代价树和最短路径树很容易混淆，因为是解决他们的Prim和Dijkstra算法的算法。 从起始顶点两种算法“生长出”，在每一个步骤中选择其连接顶点Y，它是树的顶点Z中不是边缘。 然而，虽然选择的Prim最便宜的这样的边缘，迪杰斯特拉选择这导致最短路径从X到Z上的边缘
一个简单的例子是有助于了解这些算法和它们所产生的树之间的差异。 在下面的曲线图中，从顶点的起始，二者的Prim和迪杰斯特拉开始通过选择边缘AB，然后加入边BD。 下面是其中两个算法发散：的Prim通过添加边缘DC完成树，而迪杰斯特拉增加AC或BC，因为路径AC和ABC（都与总距离30）比路径ABDC（总距离31）短。
Answer 8:
Dijkstras算法只用来寻找最短路径。
在最小生成树（普里姆的或Kruskal算法），你可以最小化边缘值最低egdes。
例如： -考虑一个情况下，你wan't创造了巨大的网络，其中U将需要大量的电线使电线的这些计数可以用最小生成树（普里姆的或Kruskal算法）来完成的（即它会给你的导线最小数目创建以最小的成本庞大的有线网络连接）。
而“Dijkstras算法”将被使用，而彼此连接的任何节点来获得两个节点之间的最短路径。
Answer 9:
@templatetypedef已覆盖MST和最短路径之间的差异。 我已经介绍的算法差异另一个所以答案通过证明两者均可使用相同的通用算法，需要一个参数作为输入来实现：函数f(u,v) 普里姆和Dijkstra算法之间的差别只是其中f(u,v)使用。
Answer 10:
在代码级别，其他不同的是API。
初始化的Prim与源顶点，S，即， Prim.new(s) ; 可以均为任何顶点，也不管S的，最终的结果，这是最小生成树（MST）的边缘是相同的。 要获取MST边缘，我们调用方法edges()
你有一个源点，S，即初始化Dijkstra算法， Dijkstra.new(s)你想获得的所有其它顶点的最短路径/距离。 最终结果，这是最短的路径/距离从s到所有其他顶点; 根据在S是不同的。 为了得到从s的最短路径/距离任何一个顶点，V，我们的方法调用distanceTo(v)和pathTo(v)分别。
文章来源: Difference between Prim's and Dijkstra's algorithms?
