title: Dijkstra Time Complexity using Binary Heap
body: <p>Let G(V, E)be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:</p>
  
  <pre><code> 1. O(|V|^2)
   2. O(|E|+|V|log|V|)
   3. O(|V|log|V|)
   4. O((|E|+|V|)log|V|)
  </code></pre>
  
  <p>========================================================================</p>
  
  <p>Correct answer is -  </p>
  
  <blockquote>
    <ol start="4">
    <li>O((|E|+|V|)log|V|)</li>
    </ol>
  </blockquote>
  
  <p>=========================================================================</p>
  
  <p>My Approach is as follows - </p>
  
  <pre><code>O(V+V+VlogV+ElogV) = O(ElogV)
  </code></pre>
  
  <ul>
  <li><code>O(V)</code> to intialize.</li>
  <li><code>O(V)</code> to Build Heap.</li>
  <li><code>VlogV</code> to perform Extract_Min</li>
  <li><code>ElogV</code> to perform Decrease Key</li>
  </ul>
  
  <blockquote>
    <p>Now, as I get O(ElogV) and when I see options, a part of me says the
    correct one is O(VlogV) because for a sparse Graph |V| = |E|, but as I
    said the correct answer is O((|E|+|V|)log|V|). So, where am I going
    wrong?</p>
  </blockquote>