retagged by
529 views
1 votes
1 votes
Time complexity of dijkstra's algorithm when array used in place of priority queue

Options

 O(V^2)  , O(VlogV+E) , O(VlogV+ElogV) , O(V^3)
retagged by

1 Answer

Best answer
5 votes
5 votes

Here is the Algorithm of Dijkstra's Shortest path Algorithm. I have taken this from GFG, to save my effort and to give you a link where you can see the implementation. On GFG, they have not discussed the Complexity, because its pretty straight forward. Let's analyze step by step. 

1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. (No Work) 
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. ( This will take $V$ time to completes its work
3) While sptSet doesn’t include all vertices (This loop Will run $V$ times )
..….a) Pick a vertex u which is not there in sptSetand has minimum distance value. (To pick a value from a matrix, we need to see all the value of the matrix, hence this step will take $ V^2 $ times
..….b) Include u to sptSet. ( It will take $1$ time )
..….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v. ( It will take $ V $ time )

Hence,

Total Time is = $ V + V * ( V^2 + 1 + V) $

                    = $ V + V^3 + V + V^2 $

                    = $ V^3 + V^2 + 2 * V $

                    = $ O (V^3) $

selected by

Related questions

0 votes
0 votes
0 answers
1
OneZero asked Nov 28, 2018
354 views
Prove dijkstra’s algorithm using Heap is O((n+|E|)logn) where n is no.of vertices and |E| is number of edges?Book : Fundamentals of Computer Algorithms By sahni pa...
1 votes
1 votes
1 answer
3
Abhinavg asked Nov 29, 2017
1,838 views
Let G(V,E) an undirected graph with positive edge weights . Dijkstras single source algorithm can be implemented using the sorted linked list data structure and adjacency...