5

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

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

4

3 回答 3

6

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

然而，在 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 必须将这些节点添加到生成的树中。

于 2013-12-05T20:38:00.270 回答
2

最小生成树不是唯一的。

Kruskal 算法选择连接两个不同的不相交 MST 组件的所有可能边中的最小长度边，目前已找到。

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

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

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

于 2013-12-05T20:02:12.053 回答
2

他们解决不同的问题。在某些情况下它们可能会生成相同的树（例如，图已经是一棵树），但通常这些树针对不同的事物进行了优化：一个从单一来源找到最短路径，另一个将总权重最小化那个树。

例如，假设我们使用 Kruskall 构建了 MST。假设 MST 权重 1 中的所有边看起来或多或少是线性的。假设从 A 到 Z 需要 5 条边，因此 MST 中从 A 到 Z 的路径将花费 5。但是，原始图也有可能具有从 A 到 Z 的边，成本为 3（< 5 )，其中 MST 不包括在内，但 Dijkstra 可能会在其结果树中占据优势。

于 2013-12-05T22:21:12.920 回答