Compute the reflexive closure and then the transitive closure of the relation below. Show the matrix after each pass of the outermost for loop.

1. 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

0 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 infinity 3

5 infinty 0 −3

infinty −1 4 0 ]