logo标签列表

Dijkstra算法和Prim算法何时会产生不同的结果？

algorithmgraphgraph-algorithmdijkstraprims-algorithm
5
我知道Prim算法和Dijkstra算法的区别。前者生成最小生成树，而后者给出从源节点到所有节点的最短路径。从数学上讲，这些不是相同的，因此我们不总是希望这两个算法产生相同的结果。
然而，在尝试不同的示例时，我得到了相同的结果。Prim算法和Dijkstra算法的伪代码看起来也非常相似。请问有人能否给我一个例子，其中Prim生成的最小生成树不能通过Dijkstra解决或反之亦然？
另外，根据我的了解，这两种算法都使用以下方法。如果我错了，请纠正我：
找到已经包括的集合中的i-j的最短路径，其中i来自已经包括的集合，j来自尚未包括的集合，然后将j添加到集合中。
2个回答
5
一个简单的例子是四个节点组成的正方形，每个角落放置一个。在任意相邻的两个角之间放置代价为2的边，沿着对角线放置代价为3的边。从任意一个角开始运行Dijkstra算法，将选取这些边：
* -- *
| \
|  \
*    *

这些是最短的路径，边的总成本为7。

运行Prim算法将选择这些边：

* -- *
| 
|
* -- *

这是一个 MST（总边缘成本为6），但这些不是最短路径（从左上角到右下角的路径成本为4，但还有一条更直接的路线可行）。
作为挑战：尝试找到以下情况的图表
- Dijkstra算法找到的最短路径树比实际MST重Ω(n)倍， - Prim算法找到的MST中，树中的路径比相应的最短路径树中的路径长Ω(n)倍。
Prim和Dijkstra都通过找到一些不在一组中的节点并将其引入该组来选择一个节点，但它们在如何调整距离方面有所不同。 在Prim算法中，使用的距离始终是组外任何节点到组内任何节点的最小距离。 在Dijkstra算法中，距离是以下值的最小值：
distance（起始节点，u）+ l（u，v）
换句话说，Dijkstra算法考虑了从起始节点到组外节点的距离，而Prim算法则没有。
希望这可以帮助你！
现在我理解了区别，感谢您的回答和编辑。 - java_doctor_101
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接