Dijkstra 和 MST 的关系
Relation between Dijkstra and MST
看到this question就想到了这个问题。为简单起见，我们可以将讨论限制在无向、加权、连通图上。很明显，如果我们从图中选择任意节点作为源，Dijkstra 不能保证生成 MST。但是，如果我们选择它作为源并应用 Dijkstra 算法，是否可以保证在一个无向的、加权的、连通的图中必须存在一个节点，从而为该图产生一个 MST？也许你可以给出一个证明或反例。谢谢！
However, is it guaranteed that there must exist one node in an
undirected, weighted, connected graph, which will produce a MST for
the graph if we choose it as the source and apply Dijkstra's
algorithm?
不，Dijkstra 算法最小化了从单个节点到所有其他节点的路径权重。最小生成树最小化将所有节点连接在一起所需的权重总和。没有理由期望这些不同的要求会产生相同的解决方案。
考虑一个完整的图，其中任意两条边的权重之和超过任意一条边的权重。这迫使 Dijkstra 总是 select 直接连接作为两个节点之间的最短路径。然后，如果图中权重最低的边并非都来自单个节点，则最小生成树将与 Dijkstra 生成的任何树都不相同。
这是一个例子：
最小生成树由权重为3（总权重为9）的三个边组成。 Dijkstra 算法返回的树将是直接连接到源节点的三条边（总权重 10 或 11）。
看到this question就想到了这个问题。为简单起见，我们可以将讨论限制在无向、加权、连通图上。很明显，如果我们从图中选择任意节点作为源，Dijkstra 不能保证生成 MST。但是，如果我们选择它作为源并应用 Dijkstra 算法，是否可以保证在一个无向的、加权的、连通的图中必须存在一个节点，从而为该图产生一个 MST？也许你可以给出一个证明或反例。谢谢！
However, is it guaranteed that there must exist one node in an undirected, weighted, connected graph, which will produce a MST for the graph if we choose it as the source and apply Dijkstra's algorithm?
不，Dijkstra 算法最小化了从单个节点到所有其他节点的路径权重。最小生成树最小化将所有节点连接在一起所需的权重总和。没有理由期望这些不同的要求会产生相同的解决方案。
考虑一个完整的图，其中任意两条边的权重之和超过任意一条边的权重。这迫使 Dijkstra 总是 select 直接连接作为两个节点之间的最短路径。然后，如果图中权重最低的边并非都来自单个节点，则最小生成树将与 Dijkstra 生成的任何树都不相同。
这是一个例子：
最小生成树由权重为3（总权重为9）的三个边组成。 Dijkstra 算法返回的树将是直接连接到源节点的三条边（总权重 10 或 11）。