algorithm - Dijkstra 和 MST 的关系

Question

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

标签： algorithmshortest-pathminimum-spanning-tree

Answer 1

但是，是否保证在无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用 Dijkstra 算法，它将为该图生成一个 MST？

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

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

这是一个例子：

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