The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.
a. True of false: T is a spanning tree of G?
b. True of false: T is a minimum spanning tree of G?
I read from Single source shortest paths problem is a problem "in which we have to find shortest paths from a source vertex v to all other vertices in the graph." I read from Partial Solutions that only one of the options is true.
From my intution and the statements above, I reasoned that a is true while b is false. This is because if T is a minimum spanning tree of G, be definition it should also be a spanning tree of G. I am trying to show that b is false with a counterexample but I can't find/draw a graph in which T isn't a min spanning tree.
Can anyone show me a counterexample to b? To me, Dijkstra's algorithm is similar to Prim's algorithm to find MSt, so in the end T should be a min spanning tree.