Analysis of Algorithms : An Active Learning Approach

7.7 PARALLEL GRAPH ALGORITHMS 207

7.7 Parallel Graph Algorithms

To explore parallel graph algorithms, we will use the representation of graphs

in an adjacency matrix form. We will explore some fascinating relationships

between matrix operations on adjacency matrices and what this means about

the related graph.

■ 7.7.1 Shortest-Path Parallel Algorithm

We said that the values of the adjacency matrix for a weighted graph would be

defined as follows:

Figure 7.7 shows a weighted graph and its corresponding adjacency matrix.

The adjacency matrix shows the direct paths between nodes of the graph,

which could be seen as the shortest paths with lengths of just one edge.

Because we are interested in knowing the shortest paths through the graph

with any number of edges, perhaps we can build up from the adjacency matrix.

If we use A^1 to represent the matrix showing the shortest paths with 1 or 0

edges (the original adjacency matrix), we can then use Aj to represent the

shortest paths with j or fewer edges. You should see that AN
^1 would be the

AdjMat[]ij,

wij

0

∞







=

ifvivj∈E

ifij=

ifvivj∉E

for all i and j in the range 1 to N

C

F

I

B

E

H

A

D

G

21

12

4

4

5

3

3

7 07 ∞∞∞∞∞∞^2

∞∞∞ ∞∞ 4 1 0 2

∞∞∞ ∞∞∞∞^01

∞ 3 40 ∞ 5

∞∞^1304

203 ∞∞ ∞ ∞∞∞

∞∞ 04 ∞∞ ∞∞∞

70 ∞∞ 13 ∞∞∞

∞∞ ∞

∞∞∞

∞∞∞∞∞ 52 ∞ 0

■FIGURE 7.7
A weighted graph
and its adjacency
matrix