title: dijkstra's algorithm running time with array and priority queue
body: <p>I'm having difficulty understanding the time of the dijkstra algorithm. Below I put the pseudo code I was analyzing for array. Considering that V are the vertices and E the edges. The Q as an array has its initialization with time O(V), the minimum and the for inside the while would have O(V) of while times O(V + E), then the result would be O(V²), am I correct?</p>
  
  <pre><code> 1  function Dijkstra(Graph, source):
      2      dist[source] ← 0                                    // Initialization
      3
      4      create vertex set Q
      5
      6      for each vertex v in Graph:           
      7          if v ≠ source
      8              dist[v] ← INFINITY                          // Unknown distance from source to v
      9              prev[v] ← UNDEFINED                         // Predecessor of v
      10
      11         Q.add_with_priority(v, dist[v])
      12
      13
      14     while Q is not empty:                              // The main loop
      15         u ← Q.extract_min()                            // Remove and return best vertex
      16         for each neighbor v of u:                      // only v that is still in Q
      17             alt ← dist[u] + length(u, v) 
      18             if alt &lt; dist[v]
      19                 dist[v] ← alt
      20                 prev[v] ← u
      21                 Q.decrease_priority(v, alt)
      22
      23     return dist[], prev[] 
  </code></pre>
  
  <p>Below I put the pseudo code I was analyzing for priority queue. Now, the Q as an priority queue has its initialization with time O(V), the minimum and the for inside the while would have O(V) of while times O(1 + ElogV), then the result would be O(VElogV), am I correct? Considering the worst case is E = (V - 1), then the result could not be O(V²logV), why the value I find on the web is O(ElogV)? why with priority queue is faster than array?</p>
  
  <pre><code>     1  function Dijkstra(Graph, source):
       2
       3      create vertex set Q
       4
       5      for each vertex v in Graph:             // Initialization
       6          dist[v] ← INFINITY                  // Unknown distance from source to v
       7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
       8          add v to Q                          // All nodes initially in Q (unvisited nodes)
       9
      10      dist[source] ← 0                        // Distance from source to source
      11      
      12      while Q is not empty:
      13          u ← vertex in Q with min dist[u]    // Node with the least distance
      14                                                      // will be selected first
      15          remove u from Q 
      16          
      17          for each neighbor v of u:           // where v is still in Q.
      18              alt ← dist[u] + length(u, v)
      19              if alt &lt; dist[v]:               // A shorter path to v has been found
      20                  dist[v] ← alt 
      21                  prev[v] ← u 
      22
      23      return dist[], prev[]
  </code></pre>