Dijkstra算法和Prim算法何时产生不同的输出？

Question

我知道Prim和Dijkstra算法之间的区别.前者产生MST,而后者产生从源到所有节点的最短路径.在数学上,这些不一样,所以我们不会总是期望这两种算法产生相同的结果.

然而,在尝试不同的例子时,我得到了相同的结果.Prim算法和Dijkstra算法的伪代码看起来非常相似.有人可以给我一个例子,其中Prim产生的MST在用Dijkstra解决时不会获得,反之亦然.

另外,据我所知.这两种算法都使用以下方法.如果我错了,请纠正我:

找到最短的ij,其中i来自已经被包含的集合,j来自尚未包含的集合,然后将j添加到集合中.

Answer 1

一个简单的例子是放置在正方形角落的四个节点的集合.将成本2的边缘放置在任意两个相邻的角之间,并将成本3的边缘对角地放在正方形上.从任何角落运行Dijkstra的算法都会选择这些边缘:

* -- *
| \
|  \
*    *

这些是最短的路径,边缘的总成本是7.

运行Prim的算法将选择这些边缘:

* -- *
| 
|
* -- *

这是一个MST(总边缘成本为6),但这些不是最短路径(从左上角到右下角的路径成本为4,但可能有更直接的路径.)

作为挑战:尝试在哪里找到图表

• Dijkstra算法找到一个比实际MST重Ω(n)倍的最短路径树,并且
• Prim的算法找到一个MST,其中树中的路径比相应的最短路径树中的路径长Ω(n)倍.

Prim和Dijkstra都通过找到一个不在一个集合中的节点并将其带入集合来选择一个节点,但它们在调整距离方面有所不同.在Prim算法中,使用的距离始终是从集合外的任何节点到集合内任何节点的最小距离.在Dijkstra的算法中,距离是以下值的最小值:

距离(起始节点,u)+ l(u,v)

换句话说,Dijkstra的算法会影响从起始节点到集合外部节点的距离,而Prim则不会.

希望这可以帮助!