for each vertex v            // O(N)
    distance[v] = Infinity      // O(1)
    previous[v] = null          // O(1)
    explored[v] = false         // O(1)
distance[s] = 0              // O(1)
repeat N times               // O(N)
    let v be unexplored vertex with smallest distance  // O(?)
    explored[v] = true          // O(1)
    for every u: unexplored neighbor(v)  // O(neighbor(v))
        d = distance[v] + weight[v,u]       // O(1)
        if d < distance[u]                  // O(1)
            distance[u] = d                 // O(1) 
            drevious[u] = v                 // O(1) 

The "for every node, for every neighbor" structure of the algorithm means that the inner steps will be repeated $\Omicron(M)$ times due to the Handshake Lemma. These steps include potentially triggering a distance update (each time in the worst case), which is implemented as a priority decrease operation in the priority queue.

The loop can stop after $N$ extractions because, in a non-duplicate priority queue with a priority update operation, each node will only appear once and be marked as visited (and its distance finalized) once extracted.

Thus, the algorithm has the following big-Oh:

O($M$t_decrease_key + $N$t_extract_min)

If we use a decrease key operation that is logarithmic, then the first term dominates, and the expression reduces to $\Omicron(M \lg N)$. This conclusion also follows if we allow for repeated vertices in the priority queue and discard extractions whose distance has been finalized. (We leave this as an exercise to prove. Hint: show $\lg M \in \Omicron(\lg N)$.)

With a data structure known as a Fibonacci heap (the implementation of which is outside the scope of this course), t_decrease_key is amortized $\Omicron(1)$. The extract minimum operation is still logarithmic, yielding the expression $\Omicron(M + N \lg N)$.