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.

Improve this question
$\endgroup$
1
  • $\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, 2015 at 4:15

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\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, 2015 at 22:42
  • 1
    $\begingroup$ @committedandroider Hi I checked the question but it seems that you already have the answer. So no problem :) $\endgroup$
    – atakanyenel
    Jun 7, 2015 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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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