Dijkstra Time Complexity using Binary Heap closed

Question

Question Source - https://gateoverflow.in/1374/gate2005-38

Let G(V,E)be an undirected graph with positive edge weights. Dijkstra’s single source shortest 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|)

========================================================================

Correct answer is -  

> 4. O((|E|+|V|)log|V|)

=========================================================================

My Approach is as follows - 

O(V+V+VlogV+ElogV) = O(ElogV)

 - O(V) to initialize.
 - O(V) to Build Heap.
 - VlogV to perform Extract_Min
 - ElogV to perform Decrease Key

> Now, as I get O(ElogV) and when I see options, a part of me says the
> correct one is O(VlogV) because for a sparse Graph |V| = |E|, but as I
> said the correct answer is O((|E|+|V|)log|V|). So, where am I going
> wrong?

Answer 1

correct one is O(VlogV) because for a sparse Graph |V| = |E|

Who said it is a Sparse Graph? Question doesn't say that. What if It were a Dense Graph?  

Comments

Yes, you're right and that's what I realized now. Thank you, Deepak Bhai ! :)

---

Always brother :)