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
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.