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

Question

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

- anuj pradhan

---

区分它们的最佳方法是阅读一些源代码，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

Answer 1

Prim算法构建一个最小生成树，该树连接图中的所有节点，并且在所有连接所有节点的树中具有最小的总成本。然而，在MST中任意两个节点之间的路径长度可能不是原始图中这两个节点的最短路径。例如，如果你想以最小的总成本为节点提供电力，那么MST非常有用。由于你只关心它们是否连接，因此两个节点之间的路径长度是否最优并不重要。

Dijkstra算法从某个源节点开始构建最短路径树。最短路径树是一棵树，将图中所有节点连接回源节点，并具有这样的属性：源节点到图中任何其他节点的路径长度都被最小化。例如，如果您想建立一个道路网络，使每个人到达某个重要地标的效率尽可能高，则此方法很有用。但是，最短路径树不能保证是最小生成树，最短路径树边上的成本之和可能比MST的成本大得多。

另一个重要的区别是算法适用于哪些类型的图形。Prim算法仅适用于无向图，因为MST的概念假定图形本质上是无向的。（对于有向图，有一种称为“最小生成树”的东西，但寻找它们的算法要复杂得多）。Dijkstra算法在有向图上也可以正常工作，因为最短路径树确实可以是有向的。此外，在包含负边缘权重的图形中，Dijkstra算法 不一定能产生正确的解决方案，而Prim算法可以处理这种情况。

- templatetypedef

---

第一段话没有意义，伙计。问题是Dijkstra和Prim之间的区别在哪里，其中Dijkstra不是关于你所说的“任何两个节点之间路径的长度”，你应该只关注为什么在Prim中源节点与任何其他节点之间的距离如果不是最短的话，那么它为什么不是最短的。我认为他一定是在问Prim中的源节点到任何其他节点。你为什么要谈论Prim中的任意两个节点？那当然不是最短的。 - JW.ZG

我已经修改了关于Dijkstra算法的段落，澄清了最短路径树仅仅是源节点出发的最短路径的最小值。我之所以这样构建我的回答是为了说明算法找到了什么而不是它们如何工作，在更高层次上展示它们产生不同结果的原因以及为什么你不应该期望它们相同。 - templatetypedef

最简单的解释在Prims算法中，您不需要指定起始节点，但在Dijkstra算法中，您必须从给定节点找到到所有其他节点的最短路径。请参阅https://dev59.com/jmYq5IYBdhLWcg3w2UIU#51605961。 - Deepak Yadav

@DeepakYadav，Prim算法的一些定义（例如CLRS）假定您实际上提供了一个起始顶点。您可以改为说，Prim返回一个最小生成树（因此解决了所述问题）无论从哪个顶点开始，而在Dijkstra中，提供不同的顶点解决了不同的（单源）最短路径问题。 - Amelio Vazquez-Reina

@templatetypedef - 当你说：“使用Dijkstra算法构建这样一棵树的成本可能比构建最小生成树的成本要高得多。”时，你能否详细说明一下？ - Amelio Vazquez-Reina

Answer 2

迪杰斯特拉算法并不会创建最小生成树，它是用来寻找最短路径的。

考虑这个图：

       5     5
  s *-----*-----* t
     \         /
       -------
         9

最短路径是9，而MST是一个不同的“路径”，长度为10。

- dfb

---

好的，谢谢您让我注意到一个重要的问题。直到现在，我一直认为Dijkstra算法生成的输出是最小生成树（MST），但是您用一个好的例子消除了我的疑惑。我清楚地看到，如果我使用类似于“Kruskal”的算法查找MST，那么我会得到您所提到的相同路径。非常感谢。 - anuj pradhan

更加准确的表达是，“最短路径长度为9”，从节点s到节点t。使用Dijkstra算法，从节点s开始运行，得到的图的权重为14（5+9）。 - Bernhard Barker

@Dukeling - 呃？在 Dijkstra 算法中，树 / 图的权重是毫无意义的，这是它的一种优点。 - dfb

非常简明扼要的说明！ - Ram Narasimhan

@dfb：通常我们只使用 Dijkstra 算法来获取两个特定顶点之间的最短路径，但实际上你可以一直运行该算法直到访问所有顶点，这将为你提供一个“最短路径树”，正如 templatetypedef 回答中所解释的那样。 - j_random_hacker

Answer 3

普里姆算法和迪杰斯特拉算法几乎相同，除了 "松弛函数"。

普里姆算法：

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)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

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)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

唯一的区别被箭头指出，就是松弛函数。

• Prim算法寻找最小生成树，只关心覆盖所有顶点的所有边的最小值。松弛函数为alt = w(u,v)
• Dijkstra算法寻找最短路径长度，因此关心边的累积。松弛函数为alt = w(u,v) + u.key

- Albert Chen

---

在代码层面，另一个区别是API。Prim算法有一个名为“edges()”的方法来返回最小生成树的边缘，而Dijkstra算法则有“distanceTo(v)”和“pathTo(v)”两个方法，分别返回从源点到顶点v的距离和路径，其中s是您初始化Dijkstra算法时选择的顶点。 - nethsix

因此，使用任何源顶点s初始化Prim算法将返回相同的edges()输出，但是使用不同的s初始化Dijkstra算法将返回不同的distanceTo(v)和pathTo(v)输出。 - nethsix

普利姆算法是否允许负权重？如果是，那么这就是另一个区别。我读到你可以通过给每个值加上大的正数来允许普利姆算法使用负权重，使所有权重都变成正数。 - Akhil Dad

解决了我的困惑！完美的答案！！ - Dhananjay Sarsonia

这里对于无向图，必须忽略处理后的顶点。 - Mr X

太棒了！我有一种直觉，这两个算法非常相似，但无法确切地指出它们的区别 - 感谢您提供这个精美的答案！ - fkotsian

Answer 4

迪杰斯特拉算法可以找到从节点i到所有节点的最小距离（您指定i）。因此，您可以得到从节点i开始的最小距离树。

普里姆算法可以为给定图形获取最小生成树。这是一棵连接所有节点的树，而所有成本的总和是可能的最小值。

因此，使用Dijkstra你可以以最小的成本从选定的节点到任何其他节点，但使用Prim's算法无法做到这一点。

- fersarr

Answer 5

我看到唯一的区别是Prim算法存储最小成本边，而Dijkstra算法存储源顶点到当前顶点的总成本。Dijkstra给出了一种从源节点到目标节点的方式，使成本最小。然而，Prim算法给出了一个最小生成树，使得所有节点都连接且总成本最小。简单来说：如果您想部署火车连接多个城市，则可以使用Prim算法。但如果您想从一个城市到另一个城市并尽可能节省时间，则应使用Dijkstra算法。

- Kevindra

Answer 6

两者都可以使用完全相同的通用算法来实现，具体如下：

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

对于Prim算法，传递f = w(u, v)，对于Dijkstra算法，传递f = u.key + w(u, v)。

另一个有趣的事情是，上面的通用算法也可以实现广度优先搜索（BFS），尽管这将是一种过度使用，因为昂贵的优先队列并不是真正必要的。要将上述通用算法转换为BFS，请传递f = u.key + 1，这与强制所有权重为1相同（即BFS给出从点A到点B所需的最小边数）。

直觉

以下是思考上述通用算法的一个好方法：我们从两个桶A和B开始。最初，将所有顶点放入B中，使桶A为空。然后我们将一个顶点从B移到A。现在看看从A中的顶点到B中的顶点的所有边缘。我们使用某些标准选择其中一个边缘，并将相应的顶点从B移动到A。重复此过程直到B为空。

一种实现这个想法的暴力方法是维护一个优先级队列，其中包含跨越到B的A中顶点的边。显然，如果图不稀疏，这将会很麻烦。所以问题是，我们是否可以维护顶点的优先级队列来代替？实际上我们可以，因为我们的最终决策是从B中选择哪个顶点。

历史背景

有趣的是，这两种算法背后的技术的通用版本在概念上早在1930年就存在了，即使当时还没有电子计算机。

故事始于Otakar Borůvka，他需要为一位家庭朋友设计一种算法，以确定如何使用最小成本的电线连接捷克共和国的摩拉维亚地区（现在）。他在1926年发表了他的算法，当时计算机科学还不存在。Vojtěch Jarník注意到了这一点，并对Borůvka的算法进行了改进，并于1930年发表了论文。事实上，他发现了我们现在所知道的Prim算法，而Prim在1957年重新发现了它。

与此无关的是，1956年，Dijkstra需要编写一个程序来展示他所在机构开发的新计算机的能力。他认为让计算机找到荷兰两个城市之间的连接非常酷。他设计了这个算法只用了20分钟。他创建了一个由64个城市组成的图表，并为这台1956年的计算机编写了代码（因为他的计算机只有6位数）。然而，他没有公开发布他的算法，因为当时还没有计算机科学期刊，他认为这可能并不是非常重要的事情。隔年，他了解到将新计算机的终端连接起来以使电线长度最小化的问题。他思考了这个问题，并重新发现了Jarník/Prim算法，这个算法再次使用了他一年前发现的最短路径算法相同的技术。他 提到 他的两个算法都是在没有使用纸笔的情况下设计的。1959年，他在一篇只有两页半的 论文 中同时发表了这两个算法。

- Shital Shah

---

谢谢！退出是模糊的，为什么即使没有发生任何事情，它也会退出循环？ - amirouche

@amirouche 我猜你说的“什么都不发生”是指if语句从未为真。在这种情况下，Q最初保存了所有key = infinity的顶点。在while循环的每次迭代中，我们出队一个顶点u。由于我们从未将任何其他顶点入队到Q中，最终Q将为空，while循环将退出。 - Joni Bekenstein

Answer 7

迪杰斯特拉算法找到起点节点到每个其他节点的最短路径。因此，你会得到从起始节点开始的最小距离树，即你可以尽可能高效地到达每个其他节点。

Prim算法为给定图获取MST，即连接所有节点的树，同时所有成本的总和是最小可能的。

简单来说，具有现实意义的例子包括：

1. 迪杰斯特拉希望通过节省旅行时间和燃料来知道到达每个目的地的最短路径。 2. Prim 希望知道如何高效部署火车铁路系统，即节省材料成本。

- Rahul

Answer 8

这是我的理解：思考算法接下来会采用哪个顶点：

Prim算法接下来采用的是最靠近树的顶点，即最靠近树上任何一个顶点的顶点。

Dijkstra算法接下来采用的是距离源点最近的顶点。

来源：R. Sedgewick关于Dijkstra算法的讲座，算法第二部分：https://coursera.org/share/a551af98e24292b6445c82a2a5f16b18

- Sonja Musicki

---

非常感谢，简洁明了的解释，正是我所需要的！ - Vesk

Answer 9

直接从迪杰斯特拉算法维基百科文章中翻译出来的内容:

迪杰斯特拉算法的过程类似于Prim算法中使用的贪婪过程。Prim的目的是找到连接图中所有节点的最小生成树；Dijkstra只关心两个节点。Prim不评估从起始节点到终点的总路径权重，而只评估单个路径的权重。

- im so confused

---

“Dijkstra 只关心两个节点”是错误的说法。 - tmyklebu

这个感觉不对。Dijkstra算法使用从起始顶点到目标顶点的累积距离。Prim算法只考虑相邻顶点的权重。 现在，为了通过回溯获得路径，这两个算法每次只使用两个顶点。例如，List parent(listLen=n, valueOfEachElement=-1); parent[neighborVertex] = currentVertex; parent是下一个节点（neighborVertex）来自于哪里的信息；请记住，图是树结构。 - undefined

Answer 10

最近我一直在困扰同一个问题，我认为我可以分享一下我的理解...

我认为这两个算法（Dijkstra和Prim）的关键差异在于它们所设计解决的问题，即两个节点之间的最短路径和最小生成树(MST)。前者是要找到从节点s到t的最短路径，并且合理的要求是每条边最多只访问一次，但不需要访问所有节点。后者则是要访问所有节点（至多一次），并且有同样的合理要求，即每条边最多只访问一次。

也就是说，Dijkstra允许我们采用“捷径”，只要我能够从s到达t，而不必担心其后果 - 一旦到达t，就完成了！虽然在MST中也有从s到t的路径，但这个s-t路径是考虑了所有其他节点的情况下创建的，因此，这条路径可能比Dijstra算法找到的s-t路径更长。以下是一个具有3个节点的快速例子：

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

假设每一个上边缘线的代价是2，底部边缘线的代价是3，则Dijktra算法会告诉我们选择底部路径，因为我们不关心中间节点。另一方面，Prim算法将返回由顶部两条边构成的最小生成树，丢弃底部边缘线。

这种差异还体现在实现方式的微妙差别上：在Dijkstra算法中，需要进行一步记录（对于每个节点）来更新从s开始的最短路径，在吸收新节点后，而在Prim算法中，则没有这种需要。

- ccy