Prim和Dijkstra算法的区别？

Question

Dijkstra和Prim的算法之间的确切区别是什么？我知道Prim会给MST,但是Dijkstra生成的树也是MST.那究竟是什么区别？

Answer 1

Prim的算法为图形构建最小生成树,该树是连接图中所有节点的树,并且在连接所有节点的所有树中具有最小总成本.但是,MST中任意两个节点之间的路径长度可能不是原始图中这两个节点之间的最短路径.例如,如果您希望物理连接图中的节点以便以最低总成本为其提供电力,则MST非常有用.两个节点之间的路径长度可能不是最佳的并不重要,因为您关心的是它们已连接的事实.

Dijkstra的算法从某个源节点开始构造最短路径树.最短路径树是将图中的所有节点连接回源节点的树,并且具有从源节点到图中任何其他节点的任何路径的长度最小化的属性.例如,如果您想要建立一个尽可能高效的道路网络,让每个人都能到达一些重要的重要里程碑,这是非常有用的.但是,最短路径树不能保证是最小生成树,并且构建这样一棵树的成本可能远大于MST的成本.

另一个重要的差异涉及算法工作的图形类型.Prim的算法仅适用于无向图,因为MST的概念假设图本质上是无向的.(对于有向图,有一种称为"最小跨越树"的东西,但找到它们的算法要复杂得多).Dijkstra的算法在有向图上可以正常工作,因为最短的路径树确实可以被定向.此外,Dijkstra的算法不一定在包含负边权重的图中产生正确的解,而Prim的算法可以处理这个问题.

希望这可以帮助!

Answer 2

Dijkstra的算法不会创建MST,它会找到最短的路径.

考虑这个图

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

最短的路径是9,而MST是10的不同"路径".

Answer 3

除了"放松功能"之外,Prim和Dijkstra算法几乎相同.

在Prim:

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) + u.key < v.key

                    v.parent = u
                    v.key = w(u,v) + u.key  <== relax function, Pay attention here

}

唯一的区别是代码的最后一行,即relax函数.搜索最小生成树的Prim只关心覆盖所有顶点的总边缘的最小值.所以它看起来像:v.key = w(u,v)Dijkstra,它搜索最小路径长度,因此它关心边缘累积.所以它看起来像:v.key = w(u,v)+ u.key

Answer 4

Dijkstra找到它的起始节点和每个其他节点之间的最短路径.因此,作为回报,您从起始节点获得最小距离树,即您可以尽可能有效地到达每个其他节点.

Prims算法为您提供给定图形的MST,即连接所有节点的树,而所有成本的总和是最小可能的.

用一个现实的例子来简化故事:

1. Dijkstra希望通过节省旅行时间和燃料来了解到每个目的地点的最短路径.
2. Prim希望了解如何有效地部署列车铁路系统,即节省材料成本.

Answer 5

这就是我感兴趣的地方：想想算法接下来采用哪个顶点：

Prim 的算法接下来采用最接近树的顶点，即最接近树上任何位置的某个顶点。

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

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

Answer 6

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

Dijkstra算法的基础过程类似于Prim算法中使用的贪婪过程.Prim的目的是找到连接图中所有节点的最小生成树; Dijkstra只关心两个节点.Prim不评估从起始节点开始的路径的总重量,仅评估单个路径.

Answer 7

我最近被同样的问题困扰，我想我可以分享我的理解......

我认为这两种算法（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 算法中，有没有这个必要。