Prim和Dijkstra算法的区别？ [英] Difference between Prim's and Dijkstra's algorithms?
问题描述
Prim的算法构造了一个最小生成树，该图是连接图中所有节点的树，并且连接所有节点的所有树中的总成本最小。但是，MST中任何两个节点之间的路径长度可能不是原始图形中这两个节点之间的最短路径。 MSTs是有用的，例如，如果你想物理连线图中的节点，以至少总成本为他们提供电力。两个节点之间的路径长度可能不是最佳的，因为你所关心的只是连接在一起的事实并不重要。
Dijkstra的算法构造一个从某个源节点开始最短路径树。最短路径树是将图中的所有节点连接到源节点的树，并且具有从源节点到图中任何其他节点的任何路径的长度最小化的属性。这是有用的，例如，如果你想建立一个尽可能高效的道路网络，让每个人都能获得一些重要的重要地标。然而，最短路径树不能保证是最小生成树，并且建立这样的树的成本可能比MST的成本大得多。
另一个重要的区别是算法工作的图形类型。 Prim的算法仅在无向图上工作，因为MST的概念假定图形本来是无向的。 （有针对性的图形有一个叫做最小跨度的东西，但是找到它们的算法要复杂得多）。 Dijkstra的算法可以在有向图上正常工作，因为实际上可以定向最短路径树。此外，Dijkstra的算法不一定在包含负边缘权重的图形中产生正确的解决方案，而Prim的算法可以处理这个。
希望这有帮助！
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'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'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 cost of building such a tree could be much larger than the cost of an MST.
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.
Hope this helps!
这篇关于Prim和Dijkstra算法的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
