Minimum Spanning Tree vs Shortest Path Tree

Is it possible to have an MST that has no common edges with the shortest path tree in an undirected graph with distinct positive edges?

I've been trying to draw out different examples, but it seems like it is impossible. The shortest path edge in the shortest path tree should also be included in an MST it seems.

---

Considering Prim's algorithm, you start from a vertex v and start connecting the other vertices to it in a manner which costs the least. So, for any other vertex u you connect to the connected component you are growing with Prim's algorithm(ie the one that includes vertex v ), although there may exist(I think) a vertex w that can reach u in a shorter distance, there is no shorter way of reaching to u from v , as Prim's algorithm dictate that you extend the connected component you start from by going to whichever node is the cheapest to add.

Consequently, as there is no shorter way of reaching from v to u , there must be at least 1 edge common in MST generated by starting from v and the shortest path tree of v .

Even if the roots of the node of MST(say, rootA ) and shortest path tree(say, rootB ) differ, while building MST, Prim's algorithm should reach rootB using an edge that is on the shortest path from rootB to rootA on the shortest path tree, as by its definition the shortest path tree should help rootB reach rootA in the shortest way possible.

链接地址: http://www.djcxy.com/p/35270.html

上一篇: MST和一项索赔？

下一篇: 最小生成树与最短路径树