Prim 和 Dijkstra 算法的区别？

Dijkstra 和 Prim 的算法到底有什么不同？我知道 Prim’s 将给出一个 MST，但是 Dijkstra 生成的树也将是一个 MST。那到底有什么区别呢？

121702 次浏览
小开

Dijkstra 的算法是一个介于节点 i 和 j 之间的单源最短路问题，而 Prim 的算法是一个最小生成树问题。这些算法使用了“贪婪算法”的编程概念

如果您检查这些概念，请访问

  1. 贪婪算法讲义: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
  2. 最小生成树: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
  3. 单源最短路径: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf
小开

Dijsktra 的算法找到最小距离 从节点 i 到所有节点(指定 i)。因此，作为回报，您得到从节点 i 的最小距离树。

Prims 算法得到最小生成树 for a given graph。一个连接所有节点的树，而所有开销的总和是最小的。

因此，与 Dijkstra you can go from the selected node to any other with the minimum cost，你不得到这与普利姆的

小开

The only difference I see is that Prim's algorithm stores a minimum cost edge whereas Dijkstra's algorithm stores the total cost from a source vertex to the current vertex.

Dijkstra 为您提供了一条从源节点到目标节点的路径，从而使成本最小化。然而 Prim 的算法给你一个最小生成树，所有的节点都是连接的，总成本是最小的。

简而言之:

所以，如果你想部署一列火车连接几个城市，你会使用普里姆的算法。但是如果你想尽可能节省时间从一个城市到另一个城市，你会使用 Dijkstra 的算法。

小开

直接来自 Dijkstra 的算法维基百科文章:

Dijkstra 算法的基础过程类似于 Prim 算法中使用的贪婪过程。Prim 的目的是找到一个连接图中所有节点的最小生成树，而 Dijkstra 只关注两个节点。Prim 不计算来自起始节点的路径的总权重，只计算单个路径的权重。

小开

Dijkstra 的算法不创建 MST，而是寻找最短路径。

Consider this graph 

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

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

小开

Prim 的算法为图构造了一个 最小生成树，这是一个连接图中所有节点的树，并且在连接所有节点的所有树中总开销最小。然而，MST 中任意两个节点之间的路径长度可能不是原始图中这两个节点之间的最短路径。例如，如果您希望将图中的节点物理连接起来，以最低的总成本向它们提供电力，MST 就很有用。两个节点之间的路径长度可能不是最优的，这并不重要，因为您所关心的只是它们是连接的这一事实。

Dijkstra 的算法从某个源节点开始构造一个 最短路径树最短路径树。最短路径树是一种将图中所有节点连接回源节点的树，它具有从源节点到图中任何其他节点的任何路径的长度最小的性质。这是有用的，例如，如果你想建立一个道路网络，使每个人都尽可能有效地到达一些主要的重要地标。然而，最短路径树不能保证是一个最小生成树，而且最短路径树边缘的代价之和可能远远大于一个最短路径树的代价。

另一个重要的区别在于算法处理的图的类型。Prim 的算法仅适用于无向图，因为 MST 的概念假定图本质上是无向的。(有向图有一种叫做“最小生成树状图”的东西，但是找到它们的算法要复杂得多)。Dijkstra 的算法可以很好地处理有向图，因为最短路径树确实可以被定向。此外，Dijkstra 的算法 在包含负边权的图中不一定产生正确的解，而 Prim 的算法可以处理这个问题。

Hope this helps!

小开

Dijkstra 找到它的开始节点之间的最短路径 还有其他节点。因此，作为回报，你得到了从开始节点的最小距离树，也就是说，你可以尽可能有效地到达每个其他节点。

Prims 算法为给定的图获得 MST，即一个连接所有节点的树，而所有开销的总和是最小的。

To make a story short with a realistic example:

  1. Dijkstra 想知道通往每个目的地的最短路径，节省旅行时间和燃料。
  2. Prim wants to know how to efficiently deploy a train rail system i.e. saving material costs.
小开

基本算法之间的关键区别在于其不同的边缘选择准则。一般来说，它们都使用一个优先级队列来选择下一个节点，但是它们有不同的标准来选择当前处理节点的相邻节点: 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--------
...

顶点，距离的计算是第二个不同点。

小开

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

迪克斯特拉:

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
小开

@ templatetypedef 已经覆盖了 MST 和最短路径之间的差异。我在 那么回答中介绍了算法的不同之处，演示了两者都可以使用同一个通用算法来实现，该算法使用另一个参数作为输入: 函数 f(u,v)。Prim 和 Dijkstra 的算法之间的区别仅仅在于您使用的是哪个 f(u,v)。

小开

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

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

对于普里姆，传递 f = w(u, v)和对于 Dijkstra 通过 f = u.key + w(u, v)。

另一个有趣的事情是，上述 Generic 也可以实现广度优先搜索(bFS) ，尽管这样做有些过火，因为并不真正需要昂贵的优先级队列。要将上述通用算法转换为 BFS，传递 f = u.key + 1，它与将所有权值强制转换为1相同(即 BFS 给出从 A 点到 B 点遍历所需的最小边数)。

直觉

这里有一种思考上述通用算法的好方法: 我们从两个存储桶 A 和 B 开始，首先，将所有顶点放在 B 中，这样存储桶 A 就是空的。然后我们将一个顶点从 B 移动到 A。现在看看从 A 的顶点到 B 的顶点的所有边。我们从这些交叉边中选择一条边，并将相应的顶点从 B 移动到 A。重复这个过程，直到 B 为空。

实现这个想法的一种强制方法是维护 A 中的顶点的优先级队列，这个队列可以交叉到 B 中。显然，如果图不稀疏，这将是一件麻烦的事情。所以问题是我们能不能维持顶点的优先级队列？这实际上我们可以作为我们的决定，最终是从 B 中选择哪个顶点。

历史背景

有趣的是，这两种算法背后的通用技术在概念上可以追溯到1930年，即使当时还没有电子计算机。

故事开始于奥塔卡博尔 vka 谁需要一个算法的家庭朋友试图找出如何连接城市在摩拉维亚(现在的捷克共和国的一部分)以最低成本的电线。1926年，他在一本与数学有关的杂志上发表了他的算法，当时计算机科学还不存在。这引起了 Vojt ch Jarník 的注意，他想到了对 Bor vka 算法的改进，并在1930年发表了它。事实上，他发现了同样的算法，我们现在知道，作为普里姆的算法谁重新发现了它在1957年。

撇开所有这些不谈，在1956年，Dijkstra 需要写一个程序来演示他的研究所开发的一台新计算机的性能。他认为让计算机在荷兰的两个城市之间找到旅行的联系是一件很酷的事情。他在20分钟内设计出了算法。他创建了一个64个城市的简化图(因为他的计算机是6位的) ，并为这台1956年的计算机编写代码。然而，他没有发表他的算法，因为主要是没有计算机科学杂志，他认为这可能不是很重要。第二年，他学会了如何连接新计算机的终端，从而使电线的长度最小化。他思考了这个问题，重新发现了 Jarník/Prim 的算法，该算法再次使用了与他一年前发现的最短路径算法相同的技术。他认为他的两个算法都是在没有使用笔或纸的情况下设计的。1959年，他发表了两个算法在一个 纸张，只有2.5页长。

小开

在代码级别，另一个区别是 API。

你初始化 Prim 时使用了一个源顶点，即 是的，也就是 Prim.new(s); 是的可以是任何一个顶点，不管 是的是什么，最终的结果都是相同的，也就是最小生成树的边缘(mST)。为了获得 MST 边缘，我们调用方法 edges()。

You initialize Dijkstra with a source vertex, s, i.e., Dijkstra.new(s) that you want to get shortest path/distance to all other vertices. The end results, which are the shortest path/distance from s to all other vertices; are different depending on the s. To get the shortest paths/distances from s to any vertex, v, we call the methods distanceTo(v) and pathTo(v) respectively.

小开

最近我也被同样的问题困扰着，我想我可能会分享我的理解..。

我认为这两种算法(Dijkstra 和 Prim)的关键区别在于它们所要解决的问题，即两个节点之间的最短路径和最小生成树(MST)。形式上是寻找节点 是的和 T之间的最短路径，合理的要求是最多访问图的每个边一次。但是，没有要求我们访问所有节点。后者(MST)是让我们访问 全部的节点(最多一次) ，同样合理的要求，访问每个边最多一次。

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

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

Let's say each of the top edges has the cost of 2, and the bottom edge has cost of 3, then Dijktra will tell us to the take the bottom path, since we don't care about the middle node. On the other hand, Prim will return us a MST with the top 2 edges, discarding the bottom edge.

这种差异也反映在实现中的细微差异上: 在 Dijkstra 的算法中，需要有一个簿记步骤(对于每个节点) ，以便在吸收一个新节点后更新来自 是的的最短路径，而在 Prim 的算法中，没有这种需要。

小开

Dijkstras 算法 仅用于寻找最短路径。

在 最小生成树(普里姆算法或克鲁斯卡尔算法)中，你可以得到具有最小边值的最小边。

For example:- Consider a situation where you wan't to create a huge network for which u will be requiring a large number of wires so these counting of wire can be done using 最小生成树(普里姆算法或克鲁斯卡尔算法) (也就是说，它会给你最少的电线数量，以最低的成本创建巨大的有线网络连接)。

而 “ Dijkstras 算法”将用于获得两个节点之间的最短路径，同时连接任何节点彼此。

小开

最简单的解释是 在 Prims 中不指定起始节点，但是在 dijsktra 中(需要有一个起始节点)必须找到从给定节点到所有其他节点的最短路径。

小开

我突然想到的是: 想想 which vertex the algorithm takes next:

Prim 的算法接下来的顶点是 最靠近树的地方，也就是最接近 树上任何一个顶点的顶点。

Dijkstra 的算法接下来取的顶点是 最接近源头的地方。

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

小开

他们都用贪婪的方法创建树。

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

使用 Dijkstra 我们可以找到单源最短路径。目标是找到从源节点到其他节点的最短路径

普里姆的算法和迪克斯特拉的一模一样

  • 它不会跟踪从源头的距离。
  • Storing the edge that connected the front of the visited vertices to the next closest vertex.
  • 作为 Prim 算法“源”的顶点是 将成为 MST 的根基。

提交答案