Dijkstra的最小生成树是什么?

下面是一个简单的示例:

该算法的工作原理如下:

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

如果正在标记访问节点,则圆检测很容易。要查找检测到的圆的最重边,请使用常见的圆搜索算法。

笔记 :图(5)说明了为什么需要访问所有边,因为(3)已经包含生成树。但这并不是最小的。