什么是 Dijkstra 的最小生成树？

Question

我找不到 Dijkstra 最小生成树的示例算法。我已经知道 Dijkstra 的单一最短路径算法，但不知道生成树。我从 class 那里得到了简单的解释：

For each edge, add it to the tree. If a cycle is detected, remove the heaviest edge.

我已经搜索了 Internet，但找不到适合它的算法。

我可能需要自己编写代码，但我想我会问问是否有人有一个很好的例子。

有人能帮忙吗？

Answer 1

这是一个简单的例子：

算法的工作原理如下：

1. 该图有灰色边。
2. 在不检测圆的情况下添加一些边。
3. 添加垂直边缘后，算法检测到一个圆。它删除了最后一条边（红色），因为它具有最重的权重。
4. 添加水平边也会生成一个圆。由于它具有最重的重量，因此被移除。
5. 添加最后一条边也会产生一个圆，但是添加的最后一条边没有最重的权重。相反，必须删除权重为 3 的边。最小生成树由图 (5) 中的黑色边组成。

如果标记访问节点，圆检测很容易。要找到检测到的圆的最重边缘，您可以使用常见的圆搜索算法。

注：图(5)演示了为什么要访问所有的边，因为(3)已经包含了一个Spanning Tree。但它不是最小的。