Multiple choice

Let G (V,E) an undirected graph with positive edge weights. Dijkstra's single source-shortes path algorithm can be implemented using the binary heap data structure with time complexity?

  1. O(| V | 2)

  2. O(| E |) +| V | log | V |)

  3. O(| V | log | V |)

  4. O((| E |+| V |) log | V |)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Diykstra Algorithm for every vertex we consider the binary heap to find shortest path. This take V logV time. And we need to transverse each edge 1 time atleast. So overall complexity 0(E + VlogV) Which is option (2)

Keep practicing — related questions