GATE Overflow | Mock GATE | Test 1 | Question: 47

Question

Which of the following statements is/are correct with respect to Djikstra Algorithm?
(P) It always works perfectly for graphs with negative weight edges.
(Q) It does not work perfectly for graphs with negative weight cycles.
(R) It may or may not work for graphs with negative weight edges.
(S) It may not terminate if the graph has negative weight cycle
(T) It always terminates for graphs with negative weight edges.
(U) Time complexity of Djikstra algorithm becomes $O(V*E)$ if AVL tree is used instead of priority queues.

 

• A. Only P, Q, S and T are correct
• B. Only P, Q, S, T and U are correct
• C. Only Q, R, T are correct
• D. Only Q, R, S, T and U are correct

Comments

@!KARAN

Dijkstra's algorithm always terminates. With each iteration, we select one vertex and relax all it's outgoing edges. After that, we remove it, and never reinsert. This means after all the required iterations are done, Dijkstra will terminate.

With negative edge cycles, it will terminate — it just won't fetch the correct answer (which is $- ∞$ )

---

@jatin khachane 1

How come it is E+VlogV

I mean Dijkstras Algo is V*(Extract min) + E*(decrease Key)

Both Extract min and decrease key operation in AVL tree is logn

So it will become O(VlogV +ElogV)

---

https://gateoverflow.in/391960/dijkstras-algorithm-negative-weight-cycle

Answer 1

T) it always terminates for graphs with negative weight edes

 

this is certainly wrong statement, BECAUSE a neg weighted edge does not mean there's no neg weighted cycle

(( p.s. READ AGAIN ABOVE STATEMENT ))