只需要确定一下: 当我在图上运行 Dijkstra 算法时，最后我会得到一棵生成树吗？ (不一定是最小生成树)
那么Dijkstra和PRIM/Kruskal的区别在于后两种算法会返回最小生成树？
谢谢
最佳答案
你是对的，有一个条件 - 图应该有一个来自源的生成树(即 - 图中的每个顶点 v 都有一个来自给定源的路径)。
此外，正如@Henry 所评论的那样 - 您应该继续算法，直到找到所有顶点的路径，并且一旦达到目标就不要“停止”。
另请注意，Dijkstra 算法(通常是最短路径求解器)是为有向图定义的，而 MST 通常是为无向图定义的。
(请注意，将每个无向图定义为有向图很容易 - 只需为无向图中的每条边 {u,v} 添加 (u,v) 和 (v,u))
关于algorithm - 生成树作为运行 Dijkstra 算法的结果？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21725211/