2
$\begingroup$

Question

I want to analyse Dijkstra Algorithm by using different varieties of Data Structure.

My solution

  1. Adjacency matrix to Store the Graph and Binary heap for Priority Queue.

    $O(V\,\,log\,V+V^{2}\,\,log \,\,V)=O(V^{2}\,\,log \,\,V)$.

Explanation-:

In Binary Heap we have $O(log\,\,V)$ for both Extract min and decrease key.

So Extract min for $V$ vertex =$O(V\,\,log \,\,V)$ and $E$ times decrease key,but here graph is dense (Adjacency matrix) so $E=V^{2}$ so total decrease key=$O(V^{2}\,\,log \,\,V)$


  1. Adjacency matrix to Store the Graph and fibonacci heap for Priority Queue.

    $O(V\,\,log\,V+V^{2})=O(V^{2})$.

Explanation-:

In Fibonacci Heap we have $O(log\,\,V)$ for Extract min and $O(1)$ for decrease key.

So Extract min for $V$ vertex =$O(V\,\,log \,\,V)$ and $E$ times decrease key,but here graph is dense (Adjacency matrix) so $E=V^{2}$ so total decrease key=$O(V^{2})$


  1. Adjacency matrix to Store the Graph and Sorted Linked List for Priority Queue.

    $O(V\,\,*V^{}+V^{2}\,\,V)=O(V^{3})$.

Explanation-:

In Sorted Linked list we have $O(V)$ for both Extract min and $O(V)$ for decrease key.(NOT SURE)

So Extract min for $V$ vertex =$O(V^{2})$ and $E$ times decrease key,but here graph is dense (Adjacency matrix) so $E=V^{2}$ so total decrease key=$O(V^{2}*V)$

I am uncertain about point 1 and 2 and confused regarding sorted linked list's priority queue.Is there some efficent way through which i can optimize my algorithm.Can anyone please help me out to clear my confusion? Thanks in advance !

$\endgroup$
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Aug 23 '17 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.