In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks
Does a Minimum Spanning Tree entail minimum cost between 2 vertices?
0
$\begingroup$
algorithms
graph-theory
-
0Oh, I see. Thank you. – 2012-06-01
1 Answers
1
In general, one should not expect an MST to provide the shortest paths, even from a vertex used first in the construction of the MST. In addition to the counterexample of a triangle with weights 4,5,6 on edges, given by Levon Haykazyan, consider this example from Wikipedia:
The nearly-horizontal edge with weight $9$ will not be included in any MST, because the edge with weight $8$ is the better way to connect the cluster on the left to the rest of the graph. Traveling along the MST between the endpoints of this weight 9 edge takes at least 10 units.