1,372 views
3 votes
3 votes

What will be the change is Time Complexity OF Dijikstra Algorithm If Following Data Structures are used  ?

  • Priority Queue : Binary Heap  & Graph : Matrix
  • Priority Queue : Binomial Heap  & Graph : Adjacancy List
  • Priority Queue : Fibonacci Heap & Graph : Adjacancy List
  • Priority Queue : Sorted Linked List  & Graph : Matrix
  • Priority Queue : AVL Tree   & Graph : Adjacancy List 

 How to find the change in timecomplexity if one is used over the other 
 

1 Answer

Best answer
6 votes
6 votes

Ohk let me clear, Dijkstra's algorithm is just used to find the single source shortest path in the graph.

In algorithm everytime we just pop out the smallest cost vertex from the data structure and for each adjacent child we just simply update the cost of adjacent child and insert the updated cost again in our data structure and remove the old cost from the data structure.

Hence we need smallest cost from list of cost.

We need erase and insert operation. 

So it's best to work on data structure which support all these operation with best complexity , like erasing any element from set of element or inserting or extract min element from list.

Priority_queue is good for all these operation with log n factor, as it was made in the form of tree ( balanced type ) which will be able to do operation with logn complexity, 

We can use set data structure, which is also know as balance binary search tree also know as avl tree 

which can support operation with log n factor. 

Hence all of the above mentioned data structure have same behaviour in all of these operation( insert , erase , update  etc ) 

Not exactly, but almost 

AVL tree  all operation insert , search , delete in o(log N)

Fibonacci heap  delete min in o(log n) , find min in o(1) 

Operation Binary[1] Binomial[1] Fibonacci[1] Pairing[2] Brodal[3][a] Rank-pairing[5] Strict Fibonacci[6]
find-min Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
delete-min Θ(log n) Θ(log n) O(log n)[b] O(log n)[b] O(log n) O(log n)[b] O(log n)
insert O(log n) Θ(1)[b] Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
decrease-key Θ(log n) Θ(log n) Θ(1)[b] o(log n)[b][c] Θ(1) Θ(1)[b] Θ(1)
merge Θ(n) O(log n)[d] Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)

So aproximately all have similar complexity,  but in case of matrix representation of the graph it will increase the overall complexity because in case of matrix we need more space and more traversal.

While in case of adjacency list , space occupied is equivalent to number of edges that is E , which means less traversal , you can go directly from any node to its any child whithout checking the edge is present or not as in case of adjacency matrix.

selected by

Related questions

7 votes
7 votes
7 answers
1
Aspi R Osa asked Jan 11, 2016
1,921 views
Acc. to dijkstra's algorithm:What will be the shortest path from A to B ?1) When the edge of length 15 is present.2) when the edge of length 15 is removed.
1 votes
1 votes
1 answer
2
2 votes
2 votes
1 answer
3
0 votes
0 votes
0 answers
4
gate20232 asked Jan 18, 2023
443 views