Differences between Minimum Spanning Tree and Shortest Path Tree
Here is an excise:
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 apply for (b), right?
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, {abc} and {cab}.
Nevertheless, your counterexample still holds, because the MST is unique there.
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 AB and BC . No other set of edges form a minimum spanning tree.
But of course, the shortest path from A to C is AC , 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.
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 !
上一篇: 最小生成树和最短路径
下一篇: 最小生成树和最短路径树的区别