This question came to my mind when I see this question. For simplicity, we can limit our discussion to undirected, weighted, connected graphs. It is clear that Dijkstra cannot guarantee to produce a MST if we choose an arbitrary node from a graph as the source. However, is it guaranteed that there must exist one node in an undirected, weighted, connected graph, which will produce a MST for the graph if we choose it as the source and apply Dijkstra's algorithm? Maybe you can give a proof or a counterexample. Thanks!
1 Answers
However, is it guaranteed that there must exist one node in an undirected, weighted, connected graph, which will produce a MST for the graph if we choose it as the source and apply Dijkstra's algorithm?
Nope, Dijkstra's algorithm minimizes the path weight from a single node to all other nodes. A minimum spanning tree minimizes the sum of the weights needed to connect all nodes together. There's no reason to expect that those disparate requirements will result in identical solutions.
Consider a complete graph where the sum of the weight of any two edges exceeds the weight of any single edge. That forces Dijkstra to always select the direct connection as the shortest path between two nodes. Then, if the lowest weight edges in the graph don't all originate from a single node, the minimum spanning tree won't be the same as any of the trees that Dijkstra will produce.
Here's an example:
The minimum spanning tree consists of the three edges with weight 3 (total weight 9). The trees returned by Dijkstra's algorithm will be whichever three edges connect directly to the source node (total weight 10 or 11).
Related