Dark Mode

1,084 views

4 votes

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.

- Only P, Q, S and T are correct
- Only P, Q, S, T and U are correct
- Only Q, R, T are correct
- Only Q, R, S, T and U are correct

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 $- ∞$ )

2