Analysis of Algorithms : An Active Learning Approach

7.7 PARALLEL GRAPH ALGORITHMS 211

take two cycles. The last parallel block takes one comparison to see if the new

node is in the processors set and then N / p updates of closest and dis-

tance. In summary, the main processing loop has 2(N / p) + p + 1 instruc-

tions and is executed N
 1 times, giving (N
 1) * (2(N / p)+p + 1). This

works out to an O(N^2 / p) run time and a cost of p*O(N^2 / p), or O(N^2 ). As

we saw in the other cases, to achieve optimality, the number of processors

should be about N / lg N.

7.7.3

1. Give the weighted adjacency matrix for the following four graphs, and cal-
   culateA^2 ,A^4 , and A^8.

■7.7.3 EXERCISES

A B C

F G H

D E

4

11

1

2

2

2 2

5

4

4

4

4

2

2

2

3

3 3

35

3 66

a. b. A B

DE

FG

C

A B C

F G H

D E

45

4

1

22

5 24

1

1

4

2

1

3

2

2

3

5

5

2 23

c. d. A B

DE

G H

C

F