## Description

Compute the reflexive closure and then the transitive closure of the relation below. Show

the matrix after each pass of the outermost for loop.

[0 1 0 0 0

1 0 0 0 1

1 0 0 1 0

0 0 0 1 0

1 0 0 0 1]

2. Draw the directed graph defined by the adjacency matrix in problem 1. Show its

condensation graph. Reorder the vertices in the rows and columns of the reflexivetransitive

closure matrix from problem 1 in any topological order defined by the

condensation graph. Examine the resulting matrix and describe how the stronglyconnected

components are reflected in that matrix.

3. Modify Floydâ€™s all-pairs shortest paths algorithm so that k is varied in the innermost loop

instead of the outermost. Consider the following weighted graph:

V = {A, B, C, D} and E = {AB, BC, CD} with the weight of each edge being 1.

Execute the modified algorithm on this matrix associated with this graph. Is the result the

same as what Floydâ€™s algorithm would produce? Explain.

4. Use Floydâ€™s algorithm to compute the distance matrix for the digraph whose edge-weight

matrix is:

[0 2 4 3

3 0 ï‚¥ 3

5 ï‚¥ 0 âˆ’3

ï‚¥ âˆ’1 4 0]