Dijkstra's Algorithm

Dijkstra's algorithm: Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. In this section, therefore, we assume that w(u, v) ≥ 0 for each edge (u, v) ∈ E. As we shall see, with a good implementation, the running time of Dijkstra's algorithm is lower than that of the Bellman-Ford algorithm.

Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ∈ V - S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. In the following implementation, we use a min-priority queue Q of vertices, keyed by their d values.

	DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  S ← Ø
3  Q ← V[G]
4  while Q ≠ Ø
5      do u ← EXTRACT-MIN(Q)
6         S ← S ∪{u}
7         for each vertex v ∈ Adj[u]
8             do RELAX(u, v, w)

Dijkstra's algorithm relaxes edges as shown in Figure 24.6. Line 1 performs the usual initialization of d and π values, and line 2 initializes the set S to the empty set. The algorithm maintains the invariant that Q = V - S at the start of each iteration of the while loop of lines 4-8. Line 3 initializes the min-priority queue Q to contain all the vertices in V ; since S = Ø at that time, the invariant is true after line 3. Each time through the while loop of lines 4-8, a vertex u is extracted from Q = V - S and added to set S, thereby maintaining the invariant. (The first time through this loop, u = s.) Vertex u, therefore, has the smallest shortest-path estimate of any vertex in V - S. Then, lines 7-8 relax each edge (u, v) leaving u, thus updating the estimate d[v] and the predecessor π[v] if the shortest path to v can be improved by going through u. Observe that vertices are never inserted into Q after line 3 and that each vertex is extracted from Q and added to S exactly once, so that the while loop of lines 4-8 iterates exactly |V| times.

Figure 24.6: The execution of Dijkstra's algorithm. The source s is the leftmost vertex. The shortest-path estimates are shown within the vertices, and shaded edges indicate predecessor values. Black vertices are in the set S, and white vertices are in the min-priority queue Q = V - S. (a) The situation just before the first iteration of the while loop of lines 4-8. The shaded vertex has the minimum d value and is chosen as vertex u in line 5. (b)-(f) The situation after each successive iteration of the while loop. The shaded vertex in each part is chosen as vertex u in line 5 of the next iteration. The d and π values shown in part (f) are the final values.

Because Dijkstra's algorithm always chooses the "lightest" or "closest" vertex in V - S to add to set S, we say that it uses a greedy strategy. Greedy strategies are presented in detail in Greedy Algorithms, but you need not have read that chapter to understand Dijkstra's algorithm. Greedy strategies do not always yield optimal results in general, but as the following theorem and its corollary show, Dijkstra's algorithm does indeed compute shortest paths. The key is to show that each time a vertex u is added to set S, we have d[u] = δ(s, u).

(Correctness of Dijkstra's algorithm): Dijkstra's algorithm, run on a weighted, directed graph G = (V, E) with non-negative weight function w and source s, terminates with d[u] = δ(s, u) for all vertices u ∈ V.

Proof We use the following loop invariant:

At the start of each iteration of the while loop of lines 4-8, d[v] = δ(s, v) for each vertex v ∈ S.

It suffices to show for each vertex u ∈ V, we have d[u] = δ(s, u) at the time when u is added to set S. Once we show that d[u] = δ(s, u), we rely on the upper-bound property to show that the equality holds at all times thereafter.

Initialization: Initially, S = Ø, and so the invariant is trivially true.
Maintenance: We wish to show that in each iteration, d[u] = δ(s, u) for the vertex added to set S. For the purpose of contradiction, let u be the first vertex for which d[u] ≠ δ(s, u) when it is added to set S. We shall focus our attention on the situation at the beginning of the iteration of the while loop in which u is added to S and derive the contradiction that d[u] = δ(s, u) at that time by examining a shortest path from s to u. We must have u ≠ s because s is the first vertex added to set S and d[s] = δ(s, s) = 0 at that time. Because u ≠ s, we also have that S ≠ Ø just before u is added to S. There must be some path from s to u, for otherwise d[u] = δ(s, u) = ∞ by the no-path property, which would violate our assumption that d[u] ≠ δ(s, u). Because there is at least one path, there is a shortest path p from s to u. Prior to adding u to S, path p connects a vertex in S, namely s, to a vertex in V - S, namely u. Let us consider the first vertex y along p such that y ∈ V - S, and let x ∈ S be y's predecessor. Thus, as shown in Figure 24.7, path p can be decomposed as . (Either of paths p₁ or p₂ may have no edges.)