algorithm - 如何运行 Dijkestra 算法使其类似于 Prim 并生成 MST？

Question

假设我正在运行 Dijkstra 算法来访问所有节点（而不是原始初始节点和目标节点），即我正在检查是否访问了所有节点，而不是目标节点。这个算法会生成 MST（最小生成树）吗？（它类似于 Prim 吗？）

Answer 1

不。考虑一个看起来像正方形的图，三个边为 cost 1，其余的边为 cost 2。该图的 MST 具有 cost 3，但如果您在包含昂贵边的顶点上启动 Dijkstra 算法，则将采用该边，因为它是连接节点的最短路径。

很酷的 ASCII 可视化：

    1
 A------B
 |      |
1|      |1
 |      |
 C------D
    2

如果您从 开始 Dijkstra C，是从到CD的最短路径，但它不能包含在 MST 中。CD

Answer 2

如此示例图所示，它不会生成 MST：

              ... A
 .... 10 -''''    \
S                  2
 '''' 11 -....      \
              ''''' B

如果我们在节点 S 处启动 Dijkstra 算法，结果树将如下所示：

              ... A
 .... 10 -''''    
S                 
 '''' 11 -....    
              ''''' B

总边长为 21，而（在这种情况下是唯一的）MST 将是：

              ... A
 .... 10 -''''    \
S                  2
                    \
                    B

结果一共有12个。