Algorithm Design and Complexity

24.3 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) e 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.