Dijkstra 与 MST 之间的关系

Question

当我看到

这个问题时，我就想到了这个问题。为简单起见，我们可以将讨论限制在无向、加权、连通图上。很明显，如果我们从图中选择任意节点作为源，Dijkstra 不能保证生成 MST。然而，是否可以保证在一个无向、带权、连通图中一定存在一个节点，如果我们选择它作为源并应用 Dijkstra 算法，该节点将为该图生成 MST？也许你可以给出证明或者反例。谢谢！

Answer 1

但是，是否保证一个节点中一定存在一个节点？ 无向、加权、连通图，这将为 如果我们选择它作为源并应用 Dijkstra 的图形 算法？

不，Dijkstra 算法最小化了从单个节点到所有其他节点的路径权重。最小生成树最小化将所有节点连接在一起所需的权重总和。没有理由期望这些不同的需求会产生相同的解决方案。

考虑一个完整的图，其中任何两条边的权重之和超过任何单个边的权重。这迫使 Dijkstra 始终选择直接连接作为两个节点之间的最短路径。然后，如果图中权重最低的边并非全部源自单个节点，则最小生成树将与 Dijkstra 将生成的任何树都不相同。

这是一个例子：

最小生成树由权重为3的三个边组成（总权重为9）。 Dijkstra 算法返回的树将是直接连接到源节点的三个边（总权重 10 或 11）。

Answer 2

使用Dijkstra算法，我们无法找到最小生成树（MST），我们找到两个Node之间的最小成本。例如，找到源节点到图中任何其他节点之间的最小成本。