edited by
3,103 views
1 votes
1 votes

Which of the following statements is true?

  • Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights.
  • Complete graph with 4 vertices, each edges having same weights can have maximum 28 minimum cost spanning tree.
  • Rerunning Dijkstra’s algorithm on a graph V times will result in the correct shortest paths tree, even if there are negative edges (but no negative cycles).
  • None of these

how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?

edited by

1 Answer

3 votes
3 votes

S1: Wrong, because if the Edge weights are disticnt then adding a constant Value never changes the edgest in MST (though it may change the shortest path between two vertices)

S2: No of spanning tree of a complete graph of N vertices is Nn-2 here 4 =N so 16 . so WRONG

S3: WRONG 

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

But with negative weights - it might not be true. For example:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Dijkstra from A will first develop C, and will later fail to find A->B->C

so None of them are correct here

NOTE: For Negative edge wight we use Bellman -Ford 

Related questions

0 votes
0 votes
1 answer
3