0
$\begingroup$

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

  • 0
    Oh, I see. Thank you.2012-06-01

1 Answers 1

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:

MST example

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.