为什么 Kruskal 产生的树与 Dijkstra 不同？

Question

谁能解释为什么 Kruskal 产生的树与 Dijkstra 不同？

我知道 kruskal 处理边的非降序顺序，但 Dijkstra 利用了优先级队列，但仍然无法理解为什么它们的结果树不同？

Answer 1

我要说的基本区别在于，给定一组节点，Dijkstra 算法会找到 2 个节点之间的最短路径。这不一定涵盖图中的所有节点。

然而，在 Kruskal 的情况下，该算法试图覆盖所有节点，同时保持边缘成本最小。

考虑这个图：

       E
   3 / |
    B  | 3
 5 /3\ |
  /    D
A      | 2
  \    F
 1 \  / 1
    C
   2 \
      G

Dijkstra 算法将返回A-C-F-D-E源节点A和目标节点的路径，E总成本为7。然而Kruskal算法应涵盖所有的节点，因此会考虑边缘[AC]，[CG]，[CF]，[FD]，[DB]和[DE]与总成本12。

在Dijkstra算法中，不相关的节点（即那些不是在路径从源目标）将被忽略，例如，G和B在这种情况下。生成的路径当然是一棵树，但并未覆盖所有节点。可能有数百万个节点连接到G（假设它们没有连接到其他节点）不会在 Dijkstra 结果的路径中。另一方面，Kruskal 必须将这些节点添加到结果树中。

Answer 2

最小生成树不是唯一的。

Kruskal 算法选择迄今为止发现的连接两个不同的不相交 MST 组件的所有可能边中的最小长度边。

Dijkstra/Prim/Jarnik 算法选择所有边中长度最小的边，这扩展了迄今为止找到的单个 MST 分量。

在一般情况下，在每一步中，算法都会从不同的可能性集中选择最小边缘。

附言。好吧，如果OP指的是Dijkstra最短路径算法的最短路径树，那么答案是最短路径树不一定是最小生成树，算法计算不同的东西。