Prim's MST: Does the start node matter?
graph, minimum-spanning-tree, prims-algorithm
Solution
That is correct. Choosing a different starting node could give you a different spanning tree, but it will always have the same weight: the minimal possible.
Problem
I intuitively feel that if one is using Prim's algorithm to find a graph's minimum spanning tree, it doesn't matter which root node is picked - the resultant MST will have the same weight regardless. Is this correct?