Dijkstra Algorithm

Question

What is the Time Complexity of the Dijkstra when it is using Adjacency list + Array (sorted or unsorted ) ? 
If it is O( V^2 + E ) then ,
According to the General form of Adj. List :  V T(remove min) + E T(update key ) 
if we are Using Sorted Array 

• Insert: O(V) 
• Delete Min: O(1)
• Update Key: O(V)   

if we are Using UnSorted Array 

• Insert: O(1) 
• Delete Min: O(n)
• Update Key: O(V)    

So according to this Our Complexity should look like this : O(V^2  + E*V) . 
Please Resolve this Confusion . 
 

Answer 1

Dijkshtra time complexity(considering adjacency list) = E(decrease key) + V(extract min)

On sorted array; 

Decrease key operation = O(V), we can directly update key but rearranging them might take O(V) time

Extract minimum= O(1), we can directly extract minimum as it was a sorted array

so modified version of Dijkshtra Algo time complexity = E(V) + V(1) = EV + V

now coming to a tricky part, we can clearly see time complexity depends upon edges and vertices so considering graph structure we have 2 choices,

• Sparse graph where Number of edges E approaches V, E ≈ | V |
• Dense graph where number of edges E approaches to V², E ≈ | V² |

let's update modified Dijkshtra Algo time complexity again by substituting values of E = EV + V

                                                                                                                                       = V².V + V = O(V³)

 

Dijlshtra Algo time complexity(Sorted Array + Adj List) = O(V³)

 

On Unsorted array;

 

Decrease key operation = O(1), directly go to array index and update, no need to rearrange here

Extract minimum= O(V), one full scan required

Dijkshtra time complexiy = E(1) + V(V) = O(E + V²)

Now again, considering graph structure we have 2 choices,

• Sparse graph where number of edges E approaches V, E ≈ | V |
• Dense graph where number of edges E approaches to V², E ≈ | V² |

Dijkshtra time complexiy(Unsorted Array + Adj list) = O(E + V²) = O(V² + V²) = O(V²)