Question discussion

[Added later – this question is not part of the original paper]What is the time complexity of Dijkstra’s algorithm for a graph with V verti…

360080Medium DSSSB TGT Computer Science 0 replies 0 views
0

[Added later – this question is not part of the original paper]

What is the time complexity of Dijkstra’s algorithm for a graph with V vertices and E edges when a binary heap (priority queue) is used?

  • AO(V)
  • BO(V + E)
  • CO((V + E) log V)
  • DO(V³)
Correct answer: C

Explanation

With a binary heap each edge relaxation and vertex extraction costs O(log V), so the total time is O((V + E) log V). (Added later – not part of the original paper.)

Discussion 0

Nobody has replied yet. Start the discussion!