1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suggest editing the question to ask only about the part you care about. You already know about part a, so why is that included in this question? And others won't care about your specific exercise. Instead, phrase the question as a conceptual question about the specific thing you are confused about. Then, tell us what you've tried and what your thoughts are. You want to find a counterexample -- what have you tried? Normally you should try all graphs up to a small minimum size -- have you tried that? Please show your research in the question. $\endgroup$ – D.W. Jun 7 '15 at 4:15
4
$\begingroup$

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

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

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.