之间是什么Dijkstra的和Prim算法的具体差异。我知道普里姆的将给予MST但Dijkstra算法生成的也将是一个MST树。那么什么是准确的区别？

What is the exact difference between Dijkstra's and Prim's algorithm. 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的长度可能不是在原始图表这两个节点之间的最短路径。 MSTS是有用的，例如，如果你想以物理连线了节点在图中，以提供电力给他们在至少总成本。这不要紧，两个节点之间的路径长度可能不是最佳的，因为所有你关心的是，他们连这个事实。

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 and has the property that the length of any path from some start 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.

另一个重要区别的担忧是什么类型的图形算法工作。 Prim算法适用于只无向图，由于MST的概念，假定图本质上是无向的。 （也有一些是所谓的最小生成树树状对于有向图，但算法来找到他们要复杂得多）。 Dijkstra算法将正常工作在向图，因为最短路径树的确可以定向。此外，Dijkstra算法does不一定产生含负边权重图的正确的解决方案，而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.

希望这有助于！