Data-Structures-And-Algorithms-Alfred-V-Aho

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

{ some action on w }

To implement such a step, we need the notion of an index type for the set of vertices adjacent to some one vertex v. For example, if adjacency lists are used to represent the graph, then an index is really a position on the adjacency list for v. If an adjacency matrix is used, an index is an integer representing an adjacent vertex. We need the following three operations on directed graphs.

1.FIRST(v) returns the index for the first vertex adjacent to v. The index for the null vertex Λ is returned if there is no vertex adjacent to v.

2.NEXT(v, i) returns the index after index i for the vertices adjacent to v. Λ is returned if i is the last index for vertices adjacent to v.

3.VERTEX(v, i) returns the vertex with index i among the vertices adjacent to v.

Example 6.5. If the adjacency matrix representation is chosen, VERTEX(v, i) returns i. FIRST(v) and NEXT(v, i) can be written as in Fig. 6.6 to operate on an externally defined n x n boolean matrix A. We assume A is declared

array [1..n, 1..n] of boolean

and that 0 is used for Λ. We can then implement the statement (6.1) as in Fig. 6.7. Note that FIRST(v) can also be implemented as NEXT(v, 0).

function FIRST ( v: integer ): integer; var

i: integer; begin

for i := 1 to n do if A[v, i] then return (i);

return (0) { if we reach here, v has no adjacent vertex } end; { FIRST }

function NEXT ( v: integer; i: integer ): integer; var

j: integer; begin

for j := i + 1 to n do if A[v, j] then

return (j); return (0)

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (5 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

end; { NEXT }

Fig. 6.6. Operations to scan adjacent vertices.

i := FIRST(v);

while i <> Λ do begin w := VERTEX(v, i); { some action on w } i := NEXT(v, i)

end

Fig. 6.7. Iteration over vertices adjacent to v.

6.3 The Single Source Shortest Paths

Problem

In this section we consider a common path-finding problem on directed graphs. We are given a directed graph G = (V, E) in which each arc has a nonnegative label, and one vertex is specified as the source. Our problem is to determine the cost of the shortest path from the source to every other vertex in V, where the length of a path is just the sum of the costs of the arcs on the path. This problem is often called the single-source shortest paths problem.† Note that we shall talk of paths as having "length" even if costs represent something different, like time.

We might think of G as a map of airline flights, in which each vertex represents a city and each arc v → w an airline route from city v to city w. The label on arc v → w is the time to fly from v to w.‡ Solving the single-source shortest paths problem for this directed graph would determine the minimum travel time from a given city to every other city on the map.

To solve this problem we shall use a "greedy" technique, often known as Dijkstra's algorithm. The algorithm works by maintaining a set S of vertices whose shortest distance from the source is already known. Initially, S contains only the source vertex. At each step, we add to S a remaining vertex v whose distance from the source is as short as possible. Assuming all arcs have nonnegative costs, we can always find a shortest path from the source to v that passes only through vertices in S. Call such a path special. At each step of the algorithm, we use an array D to record the length of the shortest special path to each vertex. Once S includes all vertices, all paths are "special," so D will hold the shortest distance from the source to each

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (6 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

vertex.

The algorithm itself is given in Fig. 6.8. It assumes that we are given a directed graph G = (V, E) where V = {1, 2, . . . , n} and vertex 1 is the source. C is a twodimensional array of costs, where C[i, j] is the cost of going from vertex i to vertex j on arc i ® j. If there is no arc i ® j, then we assume C[i, j] is ¥, some value much larger than any actual cost. At each step D [i] contains the length of the current shortest special path to vertex i.

Example 6.6. Let us apply Dijkstra to the directed graph of Fig. 6.9. Initially, S = {1}, D[2] = 10, D[3] = ¥, D[4] = 30 and D[5] = 100. In the first iteration of the forloop of lines (4)-(8), w = 2 is selected as the vertex with the minimum D value. Then we set D[3] = min(¥, 10+50)= 60. D(4) and D(5) do not change, because reaching them from 1 directly is shorter than going through vertex 2. The sequence of D- values after each iteration of the for-loop is shown in Fig. 6.10.

If we wish to reconstruct the shortest path from the source to each vertex, then we can maintain another array P of vertices, such that P [v] contains the vertex immediately before vertex v in the shortest path. Initialize P[v] to 1 for all v ¹ 1. The P-array can be updated right after line (8) of Dijkstra. If D[w]+C[w,v]<D[v] at line (8), then we set P[v]:= w. Upon termination

procedure Dijkstra;

{ Dijkstra computes the cost of the shortest paths from vertex 1 to every vertex of a directed graph }

begin

(1)S := {1};

(2)for i := 2 to n do

(3)	D[i] := C[1, i]; { initialize D }

(4)for i := 1 to n-1 do begin

(5)	choose a vertex w in V-S such that
	D[w] is a minimum;
(6)	add w to S;
(7)	for each vertex v in V-S do
(8)	D[v] := min(D[v], D[w] +
C[w, v])

end

end; { Dijkstra }

Fig. 6.8. Dijkstra's algorithm.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (7 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

Fig. 6.9. Digraph with labeled arcs.

of Dijkstra the path to each vertex can be found by tracing backward the predecessor vertices in the P-array.

Example 6.7. For the digraph in Example 6.6 the P-array would have the values P[2] = 1, P[3] = 4, P[4] = 1, and P[5] = 3. To find the shortest path from vertex 1 to vertex 5, for example, we would trace the predecessors in reverse order beginning at vertex 5. From the P-array we determine 3 is the predecessor of 5, 4 the predecessor of 3, and 1 the predecessor of 4. Thus the shortest path from vertex 1 to vertex 5 is 1, 4, 3, 5.

Fig. 6.10. Computation of Dijkstra on digraph of Fig. 6.9.

Why Dijkstra's Algorithm Works

Dijkstra's algorithm is an example where "greed" pays off, in the sense that what appears locally as the best thing to do turns out to be the best over all. In this case, the locally "best" thing to do is to find the distance to the vertex w that is outside S but has the shortest special path. To see why in this case there cannot be a shorter nonspecial path from the source to w, observe Fig. 6.11. There we show a hypothetical shorter path to w that first leaves S to go to vertex x, then (perhaps) wanders into and out of S several times before ultimately arriving at w.

But if this path is shorter than the shortest special path to w, then the initial segment of the path from the source to x is a special path to x shorter than the shortest special path to w. (Notice how important the fact that costs are nonnegative is here; without it our argument wouldn't work, and in fact Dijkstra's algorithm would not work correctly.) In that case, when we selected w at line (5) of Fig. 6.8, we should have selected x instead, because D [x] was less than D [w].

To complete a proof that Fig. 6.8 works, we should verify that at all times D [v] is truly the shortest distance of a special path to vertex v. The crux of this argument is

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (8 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

in observing that when we add a new vertex w to S at line (6), lines (7) and (8) adjust D to take account of the possibility that there is now a shorter special path to v going through w. If that path goes through the old S to w and then immediately to v, its cost, D [w]+C [w, v], will be compared with D [v] at line (8), and D [v] will be reduced if the new special path is shorter. The only other possibility for a shorter special path is shown in Fig. 6.12, where the path travels to w, then back into the old S, to some member x of the old S, then to v.

But there really cannot be such a path. Since x was placed in S before w, the shortest of all paths from the source to x runs through the old S alone. Therefore, the path to x through w shown in Fig. 6.12 is no shorter than the path directly to x through S. As a result, the length of the path in Fig. 6.12 from the source to w, x, and v is no less from the old value of D [v], since D [v] was no greater than the length of the shortest path to x through S and then directly to v. Thus D [v] cannot be reduced at line (8) by a path through w and x as in Fig. 6.12, and we need not consider the length of such paths.

Fig. 6.11. Hypothetical shorter path to w.

Fig. 6.12. Impossible shortest special path.

Running Time of Dijkstra's Algorithm

Suppose Fig. 6.8 operates on a digraph with n vertices and e edges. If we use an adjacency matrix to represent the digraph, then the loop of lines (7) and (8) takes O(n) time, and it is executed n-1 times for a total time of O(n2). The rest of the algorithm is easily seen to require no more time than this.

If e is much less than n2, we might do better by using an adjacency list representation of the digraph and using a priority queue implemented as a partially

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (9 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

ordered tree to organize the vertices in V-S. The loop of lines (7) and (8) can then be implemented by going down the adjacency list for w and updating the distances in the priority queue. A total of e updates will be made, each at a cost of O(logn) time, so the total time spent in lines (7) and (8) is now O(elogn), rather than O(n2).

Lines (1)-(3) clearly take O(n) time, as do lines (4) and (6). Using the priority queue to represent V-S, lines (5)-(6) implement exactly the DELETEMIN operation, and each of the n-1 iterations of these lines requires O(logn) time.

As a result, the total time spent on this version of Dijkstra's algorithm is bounded by O(elogn). This running time is considerably better than O(n2) if e is very small compared with n2.

6.4 The All-Pairs Shortest Paths Problem

Suppose we have a labeled digraph that gives the flying time on certain routes connecting cities, and we wish to construct a table that gives the shortest time required to fly from any one city to any other. We now have an instance of the allpairs shortest paths (APSP) problem. To state the problem precisely, we are given a directed graph G = (V, E) in which each arc v ® w has a non-negative cost C[v, w]. The APSP problem is to find for each ordered pair of vertices (v, w) the smallest length of any path from v to w.

We could solve this problem using Dijkstra's algorithm with each vertex in turn as the source. A more direct way of solving the problem is to use the following algorithm due to R. W. Floyd. For convenience, let us again assume the vertices in V are numbered 1, 2 , . . . , n. Floyd's algorithm uses an n x n matrix A in which to compute the lengths of the shortest paths. We initially set A[i, j] = C[i, j] for all i ¹ j. If there is no arc from i to j, we assume C[i, j] = ¥. Each diagonal element is set to 0.

We then make n iterations over the A matrix. After the kth iteration, A[i, j] will have for its value the smallest length of any path from vertex i to vertex j that does not pass through a vertex numbered higher than k. That is to say, i and j, the end vertices on the path, may be any vertex, but any intermediate vertex on the path must be less than or equal to k.

In the kth iteration we use the following formula to compute A.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (10 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

The subscript k denotes the value of the A matrix after the kth iteration, and it should not be assumed that there are n different matrices. We shall eliminate these subscripts shortly. This formula has the simple interpretation shown in Fig. 6.13.

To compute Ak[i, j] we compare Ak- 1[i, j], the cost of going from i to j without going through k or any higher-numbered vertex, with Ak-1[i, k] + Ak- 1[k, j], the cost of going first from i to k and then from k to j, without passing through a vertex numbered higher than k. If passing through vertex k produces a cheaper path than what we had for Ak- 1[i, j], then we choose that cheaper cost for Ak[i, j].

Fig. 6.13. Including k among the vertices to go from i to j.

Example 6.8. Consider the weighted digraph shown in Fig. 6.14. The values of the A matrix initially and after the three iterations are shown in Fig. 6.15.

Fig. 6.14. Weighted digraph.

Since Ak[i, k] = Ak-1[i, k] and Ak[k, j] = Ak-1[k, j], no entry with either subscript equal to k changes during the kth iteration. Therefore, we can perform the computation with only one copy of the A matrix. A program to perform this computation on n x n matrices is shown in Fig. 6.16.

The running time of this program is clearly O(n3), since the program is basically nothing more than a triply nested for-loop. To verify that this program works, it is easy to prove by induction on k that after k passes through the triple for-loop, A[i, j] holds the length of the shortest path from vertex i to vertex j that does not pass through a vertex numbered higher than k.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (11 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

Fig. 6.15. Values of successive A matrices.

procedure Floyd ( var A: array[1..n, 1..n] of real;

C: array[1..n, 1..n] of real );

{ Floyd computes shortest path matrix A given arc cost matrix C } var

i, j, k: integer; begin

for i := 1 to n do for j := 1 to n do

A[i, j] := C[i, j]; for i:= 1 to n do

A[i, i] := 0; for k:= 1 to n do

for i := 1 to n do for j:= 1 to n do

if A[i, k] + A[k, j] < A

[i, j] then

A[i, j] := A[i, k] + A[k,

j]

end; { Floyd }

Fig. 6.16. Floyd's algorithm.

Comparison Between Floyd's and

Dijkstra's Algorithms

Since the adjacency-matrix version of Dijkstra finds shortest paths from one vertex in O(n2) time, it, like Floyd's algorithm, can find all shortest paths in O(n3) time. The compiler, machine, and implementation details will determine the constants of proportionality. Experimentation and measurement are the easiest way to ascertain the best algorithm for the application at hand.

If e, the number of edges, is very much less than n2, then despite the relatively

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (12 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

low constant factor in the O(n3) running time of Floyd, we would expect the adjacency list version of Dijkstra, taking O(ne logn) time to solve the APSP, to be superior, at least for large sparse graphs.

Recovering the Paths

In many situations we may want to print out the cheapest path from one vertex to another. One way to accomplish this is to use another matrix P, where P[i, j] holds that vertex k that led Floyd to find the smallest value of A[i, j]. If P[i, j]=0, then the shortest path from i to j is direct, following the arc from i to j. The modified version of Floyd in Fig. 6.17 stores the appropriate intermediate vertices into P.

procedure shortest ( var A: array[1..n, 1..n] of real;

C: array[1..n, 1..n] of real; P: array[1..n, 1..n] of integer );

{shortest takes an n X n matrix C of arc costs and produces an n X n matrix A of lengths of shortest paths and an n X n

matrix

P giving a point in the "middle" of each shortest path } var

i, j, k: integer; begin

for i:= 1 to n do

for j := 1 to n do begin

A[i, j] := C[i, j]; P[i, j] := 0

end;

for i:= 1 to n do

A[i, i] := 0; for k := 1 to n do

for i:= 1 to n do for j:= 1 to n do

if A[i, k] + A[k, j] <

A[i, j] then begin

A[i, j] := A[i, k] + A[k,

j];

P[i, j] := k end

end; { shortest }

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (13 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

Fig. 6.17. Shortest paths program.

To print out the intermediate vertices on the shortest path from vertex i to vertex j, we invoke the procedure path(i, j) where path is given in Fig. 6.18. While on an arbitrary matrix P, path could loop forever, if P comes from shortest, we could not, say, have k on the shortest path from i to j and also have j on the shortest path from i to k. Note how our assumption of nonnegative weights is again crucial.

procedure path ( i, j: integer ); var

k: integer; begin

k := P[i, j]; if k = 0 then return;

path(i, k); writeln(k); path(k, j)

end; { path }

Fig. 6.18. Procedure to print shortest path.

Example 6.9. Figure 6.19 shows the final P matrix for the digraph of Fig. 6.14.

Fig. 6.19. P matrix for digraph of Fig. 6.14.

Transitive Closure

In some problems we may be interested in determining only whether there exists a path of length one or more from vertex i to vertex j. Floyd's algorithm can be specialized readily to this problem; the resulting algorithm, which predates Floyd's, is called Warshall's algorithm.

Suppose our cost matrix C is just the adjacency matrix for the given digraph. That is, C[i, j] = 1 if there is an arc from i to j, and 0 otherwise. We wish to compute

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (14 of 31) [1.7.2001 19:12:41]