2,700 views
4 votes
4 votes
Assume priority queue in Dijkstra’s algorithm is implemented using a sorted link list and graph G (V, E) is represented using adjacency matrix. What is the time complexity of Dijkstra’s algorithm (Assume graph is connected)?

 

 

How to solve this kinds of problems ? Changing DS used in one algorithm . Do I need to study the entire algorithm ?

1 Answer

Best answer
8 votes
8 votes
Dijkstra algorithim uses 3 basic operations->

1.Build heap->O(V)

2.extract min->O(log V)

3.Relax operation-:decrease key-->>O(logV)

extract min will be on maximum as the number of vertices(O(V logV) and relax operation will be in Worst case on the number of edges(O(E logV)..

so tightest upper bound=O(ElogV)

now if we use sorted list-->operations are->

extract min(O(1))

decrease key-O(V)

now from above concept extract min will be on V vertices i.e O(V^2) and decrease key on maximum E edges O(EV)

so tightest upper bound =O(VE)

in worst case E=V^2..

so time complexity=O(V^2*V)=O(V^3)
selected by

Related questions

6 votes
6 votes
1 answer
1
vaishali jhalani asked Nov 5, 2016
2,996 views
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
1 votes
1 votes
1 answer
3
Souvik33 asked Dec 19, 2022
675 views
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE
0 votes
0 votes
0 answers
4