我知道 Prim 算法和 Dijkstra 算法之间的区别。前者产生一个 MST，而后者给出从源到所有节点的最短路径。从数学上讲，它们并不相同，因此我们并不总是期望这两种算法产生相同的结果。
但是，在尝试不同的示例时，我得到了相同的结果。Prim 算法和 Dijkstra 算法的伪代码看起来也非常相似。有人可以给我一个例子，其中 Prim 产生的 MST 在使用 Dijkstra 解决时无法获得，反之亦然。
另外，据我所知。这两种算法都使用以下方法。如果我错了，请纠正我：
找到最短的 ij，其中 i 来自已包含的集合和 j 来自尚未包含的集合，然后将 j 添加到集合中。
一个简单的例子是放置在正方形角落的四个节点的集合。将成本 2 的边放置在任意两个相邻角之间，并将成本 3 的边沿对角线穿过正方形。从任何角落运行 Dijkstra 算法都会选择这些边：
* -- *
| \
| \
* *
这些是最短路径，边的总成本为 7。
运行 Prim 的算法将选择这些边缘：
* -- *
|
|
* -- *
这是一个 MST（总边缘成本为 6），但这些不是最短路径（从左上角到右下角的路径成本为 4，但可能有更直接的路线。）
作为一个挑战：尝试找到图表
Prim's 和 Dijkstra's 都通过找到不在集合中的某个节点并将其带入集合来选择节点，但它们在调整距离的方式上有所不同。在 Prim 算法中，使用的距离始终是从集合外的任何节点到集合内的任何节点的最小距离。在 Dijkstra 算法中，距离是以下值的最小值：
距离（起始节点，u）+ l（u，v）
换句话说，Dijkstra 的算法考虑了从起始节点到集合外节点的距离，而 Prim 没有。
希望这可以帮助！
考虑 ab 的长度为 100，ac 的长度为 100，bc 的长度为 1。以 a 为根的最短路径树是 ab 和 ac。mst 是 bc 和其他边之一。链接：使用深度优先搜索创建 MST？.