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 soumayan bandhu commented Jan 1, 2019 reply Follow Share What will be the time complexity if we use AVL tree? 0 votes 0 votes !KARAN commented Jan 6, 2019 i edited by !KARAN Jan 7, 2019 reply Follow Share @Ruturaj Mohanty Sir please justify this why option S is false. Dijkstra's algorithm is not suitable for graphs containing negative edge weight as there will be cycle due to negative edge weights due to which it will not stop if it is reachable from the source. But here in the question it is not mentioned that cycle is reachable or not. So ideally we should consider that a cycle may exist due to negative edge weights and are reachable from source node. Hence option S should be correct 0 votes 0 votes Ruturaj Mohanty commented Jan 7, 2019 reply Follow Share Whatever you consider, djikstra algorithm will always terminate !!!... implement it in code and see if you have doubts. Thats the best way to learn. Dont memorize thing!!! 0 votes 0 votes jatin khachane 1 commented Jan 10, 2019 reply Follow Share @Ruturaj Mohanty if AVL used then TC will be O(E+VlogV) Relax edge O(1) and extract min ==> leftmost element in left subtree O(Logv) as height = log v is this right ? 0 votes 0 votes Ruturaj Mohanty commented Jan 10, 2019 reply Follow Share Depends upon your implementation. O(ElogV)... 0 votes 0 votes 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.