SKEDSOFT

Design Analysis Of 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 p2 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 p2), we have δ(s, y) δ(s, u), and thus

  •  

    But because both vertices u and y were in V - S when u was chosen in line 5, we have d[u] d[y]. Thus, the two inequalities in (24.2) are in fact equalities, giving

    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 min-priority queue Q by calling three priority-queue operations: INSERT (implicit in line 3), EXTRACT-MIN (line 5), and DECREASE-KEY (implicit in RELAX, which is called in line 8). INSERT is invoked once per vertex, as is EXTRACT-MIN. 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 7-8 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| DECREASE-KEY operations. (Observe once again that we are using aggregate analysis.)

The running time of Dijkstra's algorithm depends on how the min-priority queue is implemented. Consider first the case in which we maintain the min-priority 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 DECREASE-KEY operation takes O(1) time, and each EXTRACT-MIN operation takes O(V) time (since we have to search through the entire array), for a total time of O(V2 E) = O(V2).

If the graph is sufficiently sparse-in particular, E = o(V2/ lg V)-it is practical to implement the min-priority queue with a binary min-heap. Each EXTRACT-MIN operation then takes time O(lg V). As before, there are |V| such operations. The time to build the binary min-heap is O(V). Each DECREASE-KEY 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(V2)-time implementation if E = o(V2/ lg V).

We can in fact achieve a running time of O(V lg V E) by implementing the min-priority queue with a Fibonacci heap. The amortized cost of each of the |V| EXTRACT-MIN operations is O(lg V), and each DECREASE-KEY 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 DECREASE-KEY calls than EXTRACT-MIN calls, so any method of reducing the amortized time of each DECREASE-KEY operation to o(lg V) without increasing the amortized time of EXTRACT-MIN would yield an asymptotically faster implementation than with binary heaps.

Dijkstra's algorithm bears some similarity to both breadth-first search and Prim's algorithm for computing minimum spanning trees. It is like breadth-first search in that set S corresponds to the set of black vertices in a breadth-first search; just as vertices in S have their final shortest-path weights, so do black vertices in a breadth-first search have their correct breadth-first distances. Dijkstra's algorithm is like Prim's algorithm in that both algorithms use a min-priority 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.