7.7 PARALLEL GRAPH ALGORITHMS 209than the number of nodes minus 1. For the graph in Fig. 7.6, we would have
all of the shortest-weight paths when we calculated A^8.
The parallel computation of the shortest path in a graph can be based on
this adjacency matrix manipulation. If we modify the matrix multiplication
algorithm so that addition is replaced by taking the minimum and multiplica-
tion is replaced by addition, the resulting algorithm will calculate the matri-
ces discussed above. Using this modified matrix multiplication algorithm
withA^1 and A^1 will produce A^2 as its result, and “multiplying” A^2 and A^2
gives A^4. Our parallel shortest-path algorithm becomes nothing more than
the parallel matrix multiplication algorithm, and, so, its analysis also applies
here.
■ 7.7.2 Minimum Spanning Tree Parallel Algorithm
You will recall that the Dijkstra-Prim minimum spanning tree (MST) algo-
rithm slowly builds the tree by adding the node connected to the current tree
by the edge with the smallest weight. The algorithm did this task from the per-
spective of the MST looking at those nodes that were connected to it and plac-
ing those in the “fringe.” With the power of multiple processors, we can instead
look at the tree from the perspective of all of the nodes and see which is closest
at each pass.
Our algorithm will be designed with p processors. Because p will be less
than the number of nodes in the graph, each processor will be responsible for
N / p nodes. We will choose one node to start the MST, and it will be the clos-
est tree node for all of the others, because it is the one and only tree node. On
each pass, each processor will examine each of its nodes and select the one that
is closest to a node in the tree. That information will be passed by each proces-
sor to a central processor, which will choose the one with the smallest distance
overall. This node will be added to the tree and will also be broadcast to the
processors so that they can update their nodes. This process will be repeated
N 1 times as the other nodes are added to the tree.
In the following algorithm, Vj will represent the set of nodes that are the
responsibility of processor Pj, and vk will represent a single node of the graph.
We will use two arrays locally in each of the processors. The first will be
closest(v), which will hold the name of the MST node that this closest to