为什么Kruskal算法得到的树与Dijkstra算法不同？

Question

有人能解释一下为什么Kruskal算法得到的生成树与Dijkstra算法不同吗？

我知道Kruskal算法是按边的非降序列来工作的，而Dijkstra算法则利用优先队列进行操作，但仍然无法理解它们得到的生成树为什么会不同？

- HMdeveloper

---

Kruskal算法用于查找最小生成树，Dijkstra算法用于查找最短路径，因此这两种算法不是直接可比的（与A*算法与Dijkstra算法相比不同），所以我认为你的问题是无效的。 - Dai

我建议你多了解一些相关知识。这两者的区别应该很快就会变得清晰明了。 - Bernhard Barker

他可能在想Prim算法而不是Dijkstra算法吗？ - Dennis Meng

对于Prime和Kruskal算法，我认为生成的树应该是相同的。 - HMdeveloper

实际上，这个问题是大学期末考试的一部分，所以我才问它。 - HMdeveloper

正如 Chill 所提到的，MST 通常不是唯一的，而且 Prim 和 Kruskal 算法通常会找到结构不同的树。 - ile

Answer 1

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

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

考虑这张图：

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

Dijkstra算法将针对源节点A和目标节点E返回路径A-C-F-D-E，总花费为7。但是，Kruskal算法应该覆盖所有节点，因此它将考虑边[AC]、[CG]、[CF]、[FD]、[DB]和[DE]，总成本为12。

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

- Varaquilex

---

我认为OP正在考虑Dijkstra的版本，该版本从单个节点找到所有最短路径，因此结果在所有节点上生成一棵树。 - ile

Answer 2

最小生成树不是唯一的。

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

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

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

附：如果OP指的是Dijkstra最短路径算法的最短路径树，则答案是最短路径树不一定是最小生成树，这些算法计算不同的内容。

- chill

---

Prim算法通常不被称为Dijkstra算法（这很好，因为已经有一个名为Dijkstra算法的算法了）（不知道问题是在谈论哪个算法）。 - Bernhard Barker

是的，也许为了避免与最短路径混淆，不管怎样，似乎它是由Dijkstra在1959年重新发现的，假设OP特别指的是这个Dijkstra/Prim/Jarnik算法，实际上使问题有意义。 - chill

Answer 3

他们解决不同的问题。在某些情况下可能会产生相同的树（例如，图已经是一棵树），但通常这些树都是针对不同的优化目标：一个从单个源找到最短路径，另一个则最小化树的总权重。

例如，考虑使用Kruskall构建MST。假设MST中所有边的权重都为1，并且它看起来更或多或少是线性的。假设从A到Z需要5条边，因此MST中从A到Z的路径将花费5。然而，原始图可能存在一条从A到Z的边的成本为3（＜5），MST没有包括，但Dijkstra可能会在其生成的树中包含该边。

- ile