Question

1. Using Warshall’s algorithm, compute the reflexive-transitive closure of the relation below.

Show the matrix after the reflexive closure and then after each pass of the outermost for loop that computes the transitive closure.

{eq}displaystyle begin{bmatrix}

0&0&0&0&1\

1&0&0&0&0\

0&0&1&1&0\

0&0&1&0&0\

1&0&0&0&1

end{bmatrix}

{/eq}

Using the matrix, show the final result of executing Floyd’s algorithm on that matrix to produce a matrix containing path lengths.

EXPERT ANSWER

Reflexive closure of the Matrix is:

{eq}begin{bmatrix}

1 &0 &0 &0 &1 \

1&1 &0