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?