最小生成树与最短路径树
在具有不同正边缘的无向图中，有没有与最短路径树没有共同边的MST是可能的？
我一直试图画出不同的例子，但它似乎是不可能的。 最短路径树中的最短路径边缘也应该包含在MST中。
考虑Prim的算法，你从一个顶点v开始，并开始以最低成本的方式连接其他顶点。 因此，对于任何其他顶点u您连接到你与Prim算法日益增长的连接组件（即一个包含顶点v），虽然有可能存在（我认为）顶点w表示可在更短的距离到达U， 有从v到达u的 方法并不是最短的，因为Prim的算法规定，通过转到最便宜添加的节点来扩展连接组件。
因此，如存在从v到u达到没有短的方式，必须有通过从V和v的最短路径树开始生成MST常见至少 1边缘。
即使MST（比方说，rootA）和最短路径树（比如，rootB）的节点的根源不同，同时建立MST，Prim算法应使用的边缘是从rootB的最短路径上rootA最短达到rootB按照其定义，最短路径树应该以尽可能最短的方式帮助rootB达到rootA 。
链接地址: http://www.djcxy.com/p/35269.html