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]
