CODEWITHSUNDEEP
algorithmtreeshortest-pathminimum-spanning-tree
user3628240
user3628240

Reputation: 927

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.

Upvotes: 1

Views: 1427

Answers (1)

ilim
ilim

Reputation: 4547

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(i.e. 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.

Upvotes: 1

Related Questions