algorithm - Prim 和 Dijkstra 算法的区别？

Question

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

Answer 1

Prim 的算法构造了一个 minimum spanning tree对于图，它是连接图中所有节点的树，并且在连接所有节点的所有树中具有最小的总成本。但是，MST 中任意两个节点之间的路径长度可能不是原始图中这两个节点之间的最短路径。 MST 很有用，例如，如果您想要物理连接图中的节点以以最低的总成本为它们供电。两个节点之间的路径长度可能不是最优的并不重要，因为您关心的只是它们已连接这一事实。

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

另一个重要的区别是算法适用于哪些类型的图。 Prim 的算法仅适用于无向图，因为 MST 的概念假定图本质上是无向的。 (对于有向图，有一种叫做“最小跨度树状结构”的东西，但是找到它们的算法要复杂得多)。 Dijkstra 算法在有向图上运行良好，因为最短路径树确实可以被定向。此外，Dijkstra 算法 does not necessarily yield the correct solution in graphs containing negative edge weights ，而 Prim 的算法可以处理这个问题。