Differences between Minimum Spanning Tree and Shortest Path Tree

Question

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?

Feoff

How is MST is unique defined? – Aftertime

I'm asking because if "unique" means simply "there exists only one possible MST", then the question is trivial and weird because the answer for (a) applies to (b), as you said. – Aftertime

me.utexas.edu/~jensen%20/ORMM/methods/unit/network/subunits/… – Gadmann

Answer 1

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.

Tralee

Answer 2

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.

Hiatus

Answer 3

AD a)

a very simple visualization would be:

MSP in a graph:

Shortest Path between A and C:

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:

Berlinda

Answer 4

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!

Simper

Not entirely, a MST will try to use the "least possible resources" to reach all the nodes, and Shortest Path will give you the shortest path from the Origin to the Destination. Think of it as this: You have already walked 100 miles from A to B, B to C is 50 miles away, but A to C was 120 miles apart. A->C surely is shorter than A->B->C, but you would want to walk B->C, instead of going back, right? – Gadmann