CODEWITHSUNDEEP
algorithmdata-structuresgraphshortest-pathminimum-spanning-tree
Jackson Tale
Jackson Tale

Reputation: 25842

Differences between Minimum Spanning Tree and Shortest Path Tree

Here is an exercise:

Either prove the following or give a counterexample:

(a) Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?

(b) Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?

My Answer is

(a)

No, for example, for graph 0, 1, 2, 0-1 is 4, 1-2 is 2, 2-0 is 5, then 0-2’s true shortest path is 5, but the mst is 0-1-2, in mst, 0-2 is 6

(b)

My problem comes into this (b).

I don't understand how whether the MST is unique can affect the shortest path.

First, my understanding is that when the weights of edges are not distinct, multiple MST may exist at the same time, right?

Second, even if MST is unique, the answer of (a) above still applies for (b), right?

Upvotes: 17

Views: 23990

Answers (4)

PyFox
PyFox

Reputation: 373

AD a)

a very simple visualization would be:

MSP in a graph:

enter image description here

Shortest Path between A and C:

enter image description here

AD b)

I guess that the uniqueness of MSP means that there is only 1 MSP MSP in a graph. So: First) Yes, if the weights of edges are not distinct, multiple MST may exist at the same time. In case of our graph, another possible MSP would include arc D-C instead of A-B (as an example). Second) The uniqueness of MST does not influence the answer for a). As an example: enter image description here

Upvotes: 1

Kaushik Shankar
Kaushik Shankar

Reputation: 5619

So lets take a look at a very simple graph:

(A)---2----(B)----2---(C)
 \                    /
  ---------3----------

The minimum spanning tree for this graph consists of the two edges A-B and B-C. No other set of edges form a minimum spanning tree.

But of course, the shortest path from A to C is A-C, which does not exist in the MST.

EDIT

So to answer part (b) the answer is no, because there is a shorter path that exists that is not in the MST.

Upvotes: 25

Pedro
Pedro

Reputation: 1

Isn't the MST related to the start node?!
Then he is trying to get the shortest path from the MST start node. Therefore, yes, the shortest path is given by the MST starting from A!

Upvotes: 0

voidengine
voidengine

Reputation: 2579

Regarding (a), I agree.

Regarding (b), for some graphs, there may be more minimal spanning trees with the same weight. Consider a circle C3 with vertices a,b,c; weights a->b=1, b->c=2, a->c=2. This graph has two MSTs, {a-b-c} and {c-a-b}.

Nevertheless, your counterexample still holds, because the MST is unique there.

Upvotes: 6

Related Questions