Dijkstra's Algorithm

Figure 24.7: The proof of Theorem 24.6. Set S is nonempty just before vertex u is added to it. A shortest path p from source s to vertex u can be decomposed into s , where y is the first vertex on the path that is not in S and x ∈ S immediately precedes y. Vertices x and y are distinct, but we may have s = x or y = u. Path p_{2} may or may not reenter set S.
We claim that d[y] = δ(s, y) when u is added to S. To prove this claim, observe that x ∈ S. Then, because u is chosen as the first vertex for which d[u] ≠ δ(s, u) when it is added to S, we had d[x] = δ(s, x) when x was added to S. Edge (x, y) was relaxed at that time, so the claim follows from the convergence property.
We can now obtain a contradiction to prove that d[u] = δ(s, u). Because y occurs before u on a shortest path from s to u and all edge weights are nonnegative (notably those on path p_{2}), we have δ(s, y) ≤ δ(s, u), and thus

d[y] = δ(s, y) = δ(s, u) = d[u].
Consequently, d[u] = δ(s, u), which contradicts our choice of u. We conclude that d[u] = δ(s, u) when u is added to S, and that this equality is maintained at all times thereafter.

Termination: At termination, Q = Ø which, along with our earlier invariant that Q = V  S, implies that S = V. Thus, d[u] = δ(s, u) for all vertices u ∈ V.
Analysis
How fast is Dijkstra's algorithm? It maintains the minpriority queue Q by calling three priorityqueue operations: INSERT (implicit in line 3), EXTRACTMIN (line 5), and DECREASEKEY (implicit in RELAX, which is called in line 8). INSERT is invoked once per vertex, as is EXTRACTMIN. Because each vertex v ∈ V is added to set S exactly once, each edge in the adjacency list Adj[v] is examined in the for loop of lines 78 exactly once during the course of the algorithm. Since the total number of edges in all the adjacency lists is E, there are a total of E iterations of this for loop, and thus a total of at most E DECREASEKEY operations. (Observe once again that we are using aggregate analysis.)
The running time of Dijkstra's algorithm depends on how the minpriority queue is implemented. Consider first the case in which we maintain the minpriority queue by taking advantage of the vertices being numbered 1 to V. We simply store d[v] in the vth entry of an array. Each INSERT and DECREASEKEY operation takes O(1) time, and each EXTRACTMIN operation takes O(V) time (since we have to search through the entire array), for a total time of O(V^{2} E) = O(V^{2}).
If the graph is sufficiently sparsein particular, E = o(V^{2}/ lg V)it is practical to implement the minpriority queue with a binary minheap. Each EXTRACTMIN operation then takes time O(lg V). As before, there are V such operations. The time to build the binary minheap is O(V). Each DECREASEKEY operation takes time O(lg V), and there are still at most E such operations. The total running time is therefore O((V E) lg V), which is O(E lg V) if all vertices are reachable from the source. This running time is an improvement over the straightforward O(V^{2})time implementation if E = o(V^{2}/ lg V).
We can in fact achieve a running time of O(V lg V E) by implementing the minpriority queue with a Fibonacci heap. The amortized cost of each of the V EXTRACTMIN operations is O(lg V), and each DECREASEKEY call, of which there are at most E, takes only O(1) amortized time. Historically, the development of Fibonacci heaps was motivated by the observation that in Dijkstra's algorithm there are typically many more DECREASEKEY calls than EXTRACTMIN calls, so any method of reducing the amortized time of each DECREASEKEY operation to o(lg V) without increasing the amortized time of EXTRACTMIN would yield an asymptotically faster implementation than with binary heaps.
Dijkstra's algorithm bears some similarity to both breadthfirst search and Prim's algorithm for computing minimum spanning trees. It is like breadthfirst search in that set S corresponds to the set of black vertices in a breadthfirst search; just as vertices in S have their final shortestpath weights, so do black vertices in a breadthfirst search have their correct breadthfirst distances. Dijkstra's algorithm is like Prim's algorithm in that both algorithms use a minpriority queue to find the "lightest" vertex outside a given set (the set S in Dijkstra's algorithm and the tree being grown in Prim's algorithm), add this vertex into the set, and adjust the weights of the remaining vertices outside the set accordingly.