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