Dijkstra 和 Prim 算法之间的确切区别是什么？我知道 Prim 会给出一个 MST，但 Dijkstra 生成的树也将是一个 MST。那么具体的区别是什么？
问问题
111787 次
16 回答
168
Prim的算法为图构造一棵最小生成树，它是连接图中所有节点的树，在连接所有节点的所有树中总成本最小。但是，MST 中任意两个节点之间的路径长度可能不是原始图中这两个节点之间的最短路径。MST 很有用，例如，如果您想以物理方式连接图表中的节点，以最低的总成本为它们提供电力。两个节点之间的路径长度可能不是最优的并不重要，因为您关心的只是它们已连接的事实。
Dijkstra 算法从某个源节点开始构造最短路径树。最短路径树是将图中的所有节点连接回源节点的树，并且具有使从源节点到图中的任何其他节点的任何路径的长度最小化的特性。这很有用，例如，如果您想构建一个道路网络，让每个人尽可能高效地到达某个重要的重要地标。但是，最短路径树不能保证是最小生成树，最短路径树边缘的成本总和可能远大于 MST 的成本。
另一个重要的区别在于算法工作的图形类型。Prim 的算法仅适用于无向图，因为 MST 的概念假定图本质上是无向的。（有向图有一种叫做“最小跨越树状结构”的东西，但是找到它们的算法要复杂得多）。Dijkstra 的算法可以在有向图上正常工作，因为最短路径树确实可以被定向。此外，Dijkstra 的算法不一定会在包含负边权重的图中产生正确的解决方案，而 Prim 的算法可以处理这个问题。
希望这可以帮助！
于 2013-01-03T18:41:11.657 回答
94
Dijkstra 的算法不会创建 MST，它会找到最短路径。
考虑这张图
5 5
s *-----*-----* t
\ /
-------
9
最短路径是 9，而 MST 是 10 处的不同“路径”。
于 2013-01-03T17:52:35.523 回答
87
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
于 2014-09-12T03:20:33.970 回答
56
Dijsktra 的算法找到从节点 i 到所有节点（您指定 i）的最小距离。因此，作为回报，您可以从节点 i 获得最小距离树。
Prims 算法为您提供给定图形的最小生成树。一棵连接所有节点的树，而所有成本的总和是最小的。
因此，使用 Dijkstra ，您可以以最低的成本从选定的节点转到任何其他节点，而 Prim 无法做到这一点
于 2012-12-10T04:27:02.193 回答
33
我看到的唯一区别是 Prim 算法存储最小成本边，而 Dijkstra 算法存储从源顶点到当前顶点的总成本。
Dijkstra 为您提供了一种从源节点到目标节点的方式，从而使成本最小。然而，Prim 的算法为您提供了一个最小生成树，这样所有节点都连接起来并且总成本最小。
简单来说：
所以，如果你想部署一列火车连接几个城市，你会使用 Prim 的算法。但是，如果您想从一个城市到另一个城市尽可能节省时间，您会使用 Dijkstra 的算法。
于 2012-12-10T04:27:24.397 回答
26
两者都可以使用完全相同的通用算法来实现，如下所示：
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, passf = w(u, v)和对于 Dijkstra pass 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 年一样古老，即使当时还没有电子计算机。
故事从 Otakar Borůvka 开始，他需要一种算法，让一位家庭朋友试图弄清楚如何用最低成本的电线连接摩拉维亚国家（现为捷克共和国的一部分）的城市。他于 1926 年在与数学相关的期刊上发表了他的算法，因为当时还没有计算机科学。这引起了 Vojtěch Jarník 的注意，他想到了对 Borůvka 算法的改进，并于 1930 年发表了该算法。事实上，他发现了与我们现在所知的 Prim 算法相同的算法，并在 1957 年重新发现了它。
除了所有这些之外，1956 年，Dijkstra 需要编写一个程序来展示他的研究所开发的一台新计算机的能力。他认为让计算机找到在荷兰两个城市之间旅行的连接会很酷。他在 20 分钟内设计了算法。他创建了一个包含 64 个城市的图表并进行了一些简化（因为他的计算机是 6 位的），并为这台 1956 年的计算机编写了代码。但是他没有发表他的算法，因为主要是没有计算机科学期刊，他认为这可能不是很重要。第二年，他了解到连接新计算机终端的问题，以使电线的长度最小化。他思考了这个问题并重新发现了 Jarník/Prim' s 算法再次使用了与他一年前发现的最短路径算法相同的技术。他提到他的两种算法都是在不使用笔或纸的情况下设计的。1959 年，他在一篇只有 2 页半长的论文中发表了这两种算法。
于 2014-12-30T05:40:17.657 回答
15
Dijkstra 找到它的开始节点和所有其他节点之间的最短路径。因此，作为回报，您可以从起始节点获得最小距离树，即您可以尽可能高效地到达每个其他节点。
Prims 算法为您提供给定图的 MST，即连接所有节点的树，而所有成本的总和是可能的最小值。
用一个现实的例子来做一个简短的故事：
- Dijkstra 想通过节省旅行时间和燃料来了解到每个目的地的最短路径。
- Prim 想知道如何有效地部署火车轨道系统，即节省材料成本。
于 2013-01-04T06:04:19.110 回答
10
直接来自Dijkstra 算法的维基百科文章：
Dijkstra 算法的基础过程类似于 Prim 算法中使用的贪心过程。Prim 的目的是找到连接图中所有节点的最小生成树；Dijkstra 只关心两个节点。Prim's 不评估从起始节点开始的路径的总权重，仅评估单个路径。
于 2013-01-03T17:50:25.477 回答
6
我最近被同样的问题困扰，我想我可能会分享我的理解......
我认为这两种算法（Dijkstra 和 Prim）之间的主要区别在于它们旨在解决的问题，即两个节点之间的最短路径和最小生成树 (MST)。形式是找到节点s和t之间的最短路径，合理的要求是最多访问图的每条边一次。但是，它不需要我们访问所有节点。后者（MST）是让我们访问所有节点（最多一次），并且同样的合理要求也是最多访问每条边一次。
话虽如此，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 将返回给我们一个顶部 2 个边缘的 MST，丢弃底部边缘。
这种差异也反映在实现的细微差别上：在 Dijkstra 算法中，在吸收一个新节点后，需要有一个记账步骤（对于每个节点）来更新从s开始的最短路径，而在 Prim 算法中，有没有这种需要。
于 2016-10-19T13:39:38.423 回答
4
最简单的解释是在 Prims 中你没有指定起始节点，但在 dijsktra 中你（需要有一个起始节点）必须找到从给定节点到所有其他节点的最短路径。
于 2018-07-31T05:25:39.247 回答
4
这对我来说很重要：考虑一下算法接下来需要哪个顶点：
Prim 的算法采用最接近树的下一个顶点，即最接近树上任何位置的某个顶点。
Dijkstra 算法接下来采用最接近源的顶点。
资料来源：R. Sedgewick 关于 Dijkstra 算法的讲座，算法，第二部分：https ://coursera.org/share/a551af98e24292b6445c82a2a5f16b18
于 2021-08-02T13:36:41.903 回答
3
Dijkstra 算法是节点 i 和 j 之间的单源最短路径问题，而 Prim 算法是最小生成树问题。这些算法使用名为“贪婪算法”的编程概念
如果您检查这些概念，请访问
于 2012-12-10T04:22:55.450 回答
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的计算是第二个不同点。
于 2014-06-28T23:34:38.080 回答
3
Dijkstras 算法仅用于寻找最短路径。
在最小生成树（Prim 或 Kruskal 算法）中，您会得到具有最小边值的最小边值。
例如：-考虑一种情况，您不想创建一个庞大的网络，您将需要大量的电线，因此这些电线的计数可以使用最小生成树（Prim 或 Kruskal 算法）来完成 （即它将为您提供最少的电线数量，以最低的成本创建巨大的有线网络连接）。
而“Dijkstras 算法”将用于获得两个节点之间的最短路径，同时将任何节点相互连接。
于 2017-12-06T18:36:09.263 回答
0
@templatetypedef 涵盖了 MST 和最短路径之间的差异。我已经在另一个 So 答案中介绍了算法差异，通过证明两者都可以使用相同的通用算法来实现，该算法需要一个参数作为输入： function f(u,v)。Prim 和 Dijkstra 算法之间的区别仅仅是f(u,v)你使用的。
于 2014-12-30T04:07:34.233 回答
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)。
于 2016-04-24T05:38:17.007 回答