title: Dijkstra's Algorithm Runtime
body: <p>I know that this might not be a good question, but I was wondering how it's runtime is O(ElogV).</p>
  
  <p>Here's the Algo</p>
  
  <pre><code>DIJKSTRA(G,w,s)
  S=null
  PQ=G.V
  while (PQ!=null)
      u=Extract-Min(PQ)
      S=S+u \\Add node u to set S(explored vertices)
      foreach (v in adj(u))
          if(d(v) &gt; d(u) + w(u,v) )
              d(v) = d(u) + w(u,v)  \\at this step, we need to update the priority d(v) of vertex (v) in the Priority Queue. 
  </code></pre>
  
  <p>Time complexity is given by O(E logV), as the inner loop runs at most E times, and for each loop iteration, it take O(logV) time to update the priority d(v) of vertex (v) in Priority Queue PQ. But this operation requires us to search for the vertex (v) in Priority Queue PQ, which takes O(v) time. So how is the Time complexity O(E logV). </p>
  
  <p>--Edit--
  If fact the while loop is executed V times and each time an element is extracted from PQ, which means that running time is O(V logV), right?             </p>