logo标签列表

Prim算法和Dijkstra算法有什么区别？

algorithmgraphdijkstraminimum-spanning-treeprims-algorithm
129

Dijkstra算法和Prim算法的确切区别是什么？我知道Prim算法会给出MST，但由Dijkstra生成的树也将是MST。那么确切的区别是什么？

10
区分它们的最佳方法是阅读一些源代码，Dijkstra 和 Prim。主要区别在于：对于 Prim 算法，条件为 graph[u][v] < key[v]，而对于 Dijkstra 算法，条件为 dist[u]+graph[u][v] < dist[v]。因此，从这两个页面中的图表可以看出，它们之间的主要区别在于这两行代码。 - JW.ZG
可能是什么是Dijkstra算法和Prim算法的区别？的重复问题。 - e4c5
元算法的差别：我认为只有一个指定为Prim's的算法，但是有多个Dijkstra算法，其中一个因变体而臭名昭著。 - greybeard
18个回答
4
最简单的解释是，在Prim算法中，你不需要指定起始节点；而在Dijkstra算法中，你需要指定一个起始节点，并找到该节点到其他所有节点的最短路径。
这是最简单的解释，但你过于简化了。你所陈述的事实并不能解释为什么在某些应用中使用Prim算法而不是Dijkstra算法，反之亦然。 - undefined
3
基本算法之间的关键区别在于它们不同的边缘选择标准。通常，它们都使用优先队列来选择下一个节点，但是对于选择当前处理节点的相邻节点，它们有不同的标准：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 的计算是第二个不同点。
3
3

Dijkstra算法仅用于查找最短路径。

在最小生成树(Prim或Kruskal算法)中，您可以获得具有最小边值的最小边数。

例如：考虑一种情况，您想要创建一个巨大的网络，因此需要大量电线，因此可以使用最小生成树(Prim或Kruskal算法)来计算电线数量 (即它将为您提供创建巨大有线网络连接所需的最少电线数量和最低成本)。

而"Dijkstra算法"将用于在连接任何节点时获取两个节点之间的最短路径。

0

在代码层面上，另一个区别是API。

您可以使用源顶点s初始化Prim，即Prim.new(s)； s可以是任何顶点，而无论s如何，最小生成树（MST）的边缘都是相同的。要获取MST边缘，我们调用方法edges()。

您可以使用源顶点s初始化Dijkstra，即Dijkstra.new(s)，以获取到所有其他顶点的最短路径/距离。最终结果，即从s到所有其他顶点的最短路径/距离取决于s。要获取从s到任何顶点v的最短路径/距离，我们分别调用方法distanceTo(v)和pathTo(v)。

0
@templatetypedef已经讲解了MST和最短路径之间的区别。我在另一个So答案中介绍了算法的不同之处，通过演示可以使用相同的通用算法来实现两者，该算法需要一个额外的参数作为输入：函数f（u，v）。Prim算法和Dijkstra算法之间的区别仅在于您使用哪个f（u，v）。
0

它们都使用贪心算法创建树。

使用Prim算法，我们找到最小成本生成树。目标是找到覆盖所有节点的最小成本。

使用Dijkstra算法，我们找到单源最短路径。目标是找到从源到每个其他节点的最短路径。

Prim算法与Dijkstra算法完全相同，除了：

  • 它不跟踪源的距离。
  • 存储连接已访问顶点前面和下一个最近顶点的边缘。
  • 作为Prim算法的“源”使用的顶点将成为MST的根。
0
Dijkstra和Prim有一个共同点：它们都从一个节点开始，并且在每个循环中都必须选择一个节点。对于Dijkstra来说，在'dist[]'数组中具有最小值的节点被选中，而对于Prim来说，选择的节点是与具有最小权重的边相邻的节点。
在大多数情况下，它们每次循环中选择的节点是不同的。例如，对于这个图：
        *D
        |
        |4
        |
    5   |   5
A*-----*B-----*C
  \__________/
       8

从节点A开始，Prim和Dijkstra都会选择节点B。但是接下来，Prim会选择节点D，而Dijkstra会选择节点C。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接