[Solved]: Why is T not a minimum spanning tree of G?

Problem Detail: 

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.

Asked By : committedandroider

Answered By : atayenel

Vertices: {A,B,C}

Edges: (undirected) {A,B,4} {A,C,3} {B,C,2}

So basically it's a triangle with the given weights. Starting from A, Dijkstra's algorithm will give you (A,B) and (A,C) but the minimum spanning Tree will give you (A,C) and (C,B).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43324