edited by
1,585 views
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.

 

  1. Only P, Q, S and T are correct
  2. Only P, Q, S, T and U are correct
  3. Only Q, R, T are correct
  4. Only Q, R, S, T and U are correct
edited by

1 Answer

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 ))
Answer:

Related questions

2 votes
2 votes
1 answer
1
1 votes
1 votes
1 answer
2
Jithin Jayan asked Jul 23, 2016
376 views
If a graph contains a positive weight cycle reachable from source, Can we find a well defined shortest path using Dijkstra/Bellman-Ford algorithm?
1 votes
1 votes
1 answer
3
Souvik33 asked Dec 19, 2022
676 views
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE