Prim 和 Dijkstra 算法之间的区别? [英] Difference between Prim's and Dijkstra's algorithms?

问题描述

Dijkstra 和 Prim 算法之间的确切区别是什么?我知道 Prim 会提供 MST，但 Dijkstra 生成的树也将是 MST.那么具体的区别是什么?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

推荐答案

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

Prim's algorithm constructs a minimum spanning tree for the graph, which is a tree that connects all nodes in the graph and has the least total cost among all trees that connect all the nodes. However, the length of a path between any two nodes in the MST might not be the shortest path between those two nodes in the original graph. MSTs are useful, for example, if you wanted to physically wire up the nodes in the graph to provide electricity to them at the least total cost. It doesn't matter that the path length between two nodes might not be optimal, since all you care about is the fact that they're connected.

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

Dijkstra's algorithm constructs a shortest path tree starting from some source node. A shortest path tree is a tree that connects all nodes in the graph back to the source node and has the property that the length of any path from the source node to any other node in the graph is minimized. This is useful, for example, if you wanted to build a road network that made it as efficient as possible for everyone to get to some major important landmark. However, the shortest path tree is not guaranteed to be a minimum spanning tree, and the sum of the costs on the edges of a shortest-path tree can be much larger than the cost of an MST.

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

Another important difference concerns what types of graphs the algorithms work on. Prim's algorithm works on undirected graphs only, since the concept of an MST assumes that graphs are inherently undirected. (There is something called a "minimum spanning arborescence" for directed graphs, but algorithms to find them are much more complicated). Dijkstra's algorithm will work fine on directed graphs, since shortest path trees can indeed be directed. Additionally, Dijkstra's algorithm does not necessarily yield the correct solution in graphs containing negative edge weights, while Prim's algorithm can handle this.

希望这有帮助！

这篇关于Prim 和 Dijkstra 算法之间的区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！