# Why is T not a minimum spanning tree of G?

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.

– D.W.
Jun 7, 2015 at 4:15

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).

• Ahh I see thank you! can you take a look at my other graph question? cs.stackexchange.com/questions/43323/… Jun 6, 2015 at 22:42
• @committedandroider Hi I checked the question but it seems that you already have the answer. So no problem :) Jun 7, 2015 at 23:37

Well, what if you have negative edge weights? Are you sure that you'll get the MST in that case? What if your graph looks like this:

Vertices:

{A, B, C}

Edges:

(A, C, 2)
(A, B, 1)
(B, C, -2)


Where an edge is represented as (vertex1, vertex2, weight).

Wouldn't the tree returned be only the edge AC?