algorithm - 什么是 Dijkstra 的最小生成树？

Question

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

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)已经包含了生成树。但这并不是最小的。