4 votes 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 Algorithms go-mockgate-1 greedy-algorithm dijkstras-algorithm shortest-path algorithms graph-algorithm + – Ruturaj Mohanty asked Dec 27, 2018 edited Sep 10, 2020 by ajaysoni1924 Ruturaj Mohanty 1.6k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments JashanArora commented Jan 7, 2020 reply Follow Share @!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 $- ∞$ ) 2 votes 2 votes Codered03 commented Jan 26, 2022 reply Follow Share @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) 0 votes 0 votes killbill pandey commented Jan 22, 2023 reply Follow Share https://gateoverflow.in/391960/dijkstras-algorithm-negative-weight-cycle 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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 )) blackcloud answered Jan 11, 2020 blackcloud comment Share Follow See all 0 reply Please log in or register to add a comment.