Analysis of Algorithms : An Active Learning Approach

208 PARALLEL ALGORITHMS

matrix with the shortest paths through the entire graph because any path with

N or more edges must include a cycle, and so a path without the cycle would

have fewer than N edges.

We begin by thinking about how we might construct A^2 from A^1. The

shortest path with two edges between any nodes x and y will go through

exactly one of the other nodes. For example, the paths of length two between

nodes A and E go through either nodes B or D. If we look at the sum of the

weights of the edges AB and BE verses the sum of the weights of the edges AD

and DE, we see that the path through node D is shorter than the path through

node B. In general, if we looked at the sum of A* and *E, where * takes on the

value of every node from A through I (except A and E), the minimum of these

sums will be the shortest path with two edges. If we allow A and E to also be

included for the *, we would get the shortest path with two or fewer edges as

our result. This then gives the general form

Aij^2 = minimumk∈V(Aik^1 + Akj^1 )

If we apply this to the adjacency matrix of Fig. 7.7, the result is shown in

Fig. 7.8.

We could construct A^3 from A^1 and A^2 by noticing that the shortest path

with three edges or less would be a shortest path with two edges or less to

some node followed by a shortest path of length one edge or less from that

node to the destination, or vice versa. We could construct A^4 either from A^1

andA^3 or from just A^2. Because of this, we can get to our result more quickly

by just calculating A^2 ,A^4 ,A^8 ,... , AN, where N is the power of 2 just greater

07 ∞∞∞∞ 2510

∞ 5 ∞ 774 1 0 2

∞∞∞ ∞ ∞ 5 0 13

10 3 4407 ∞ 5

530461 ∞ 4 5

(^24) ∞∞∞ (^03) ∞ 7
∞ 790 ∞∞ 4 ∞∞
707413 ∞ 58
∞
∞ 89 ∞ 6 5 3 20
■FIGURE 7.8
A^2 for the weighted
graph of Fig. 7.7