Consider a relation R=\{ (1,1),(1, 3), (2,2), (2,3), (3,1)\} R = {( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 1 )} on the set A=\{1,2,3\} A = { 1 , 2 , 3 } .
Let us state the steps of the Warshall's algorithm:
1. Let W:=M_R,\ k:=0. W := M R , k := 0.
2. Put k:=k+1. k := k + 1.
3. For all i\ne k i = k such that w_{ik}=1 w ik = 1 and for all j j let w_{ij}=w_{ij}\lor w_{kj}. w ij = w ij ∨ w kj .
4. If k=n k = n then stop and W=M_{R^*}, W = M R ∗ , else go to step 2.
Let us find transitive closure of the relation R R using Warshall's algorithm:
W^{(0)}=M_R =\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 0 \end{pmatrix} W ( 0 ) = M R = ⎝ ⎛ 1 0 1 0 1 0 1 1 0 ⎠ ⎞
W^{(1)} =\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} W ( 1 ) = ⎝ ⎛ 1 0 1 0 1 0 1 1 1 ⎠ ⎞
W^{(2)} =\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} W ( 2 ) = ⎝ ⎛ 1 0 1 0 1 0 1 1 1 ⎠ ⎞
M_{R^*}=W^{(3)} =\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} M R ∗ = W ( 3 ) = ⎝ ⎛ 1 1 1 0 1 0 1 1 1 ⎠ ⎞
It follows that R^*=\{ (1,1),(1, 3), (2,1),(2,2), (2,3), (3,1),(3,3)\}. R ∗ = {( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 1 ) , ( 3 , 3 )} . Consider a relation
R=\{ (1,1),(1, 3), (2,2), (2,3), (3,1)\} R = {( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 1 )} on the set A=\{1,2,3\} A = { 1 , 2 , 3 } .
Let us state the steps of the Warshall's algorithm:
1. Let W:=M_R,\ k:=0. W := M R , k := 0.
2. Put k:=k+1. k := k + 1.
3. For all i\ne k i = k such that w_{ik}=1 w ik = 1 and for all j j let w_{ij}=w_{ij}\lor w_{kj}. w ij = w ij ∨ w kj .
4. If k=n k = n then stop and W=M_{R^*}, W = M R ∗ , else go to step 2.
Let us find transitive closure of the relation R R using Warshall's algorithm:
W^{(0)}=M_R =\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 0 \end{pmatrix} W ( 0 ) = M R = ⎝ ⎛ 1 0 1 0 1 0 1 1 0 ⎠ ⎞
W^{(1)} =\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} W ( 1 ) = ⎝ ⎛ 1 0 1 0 1 0 1 1 1 ⎠ ⎞
W^{(2)} =\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} W ( 2 ) = ⎝ ⎛ 1 0 1 0 1 0 1 1 1 ⎠ ⎞
M_{R^*}=W^{(3)} =\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix} M R ∗ = W ( 3 ) = ⎝ ⎛ 1 1 1 0 1 0 1 1 1 ⎠ ⎞
It follows that R^*=\{ (1,1),(1, 3), (2,1),(2,2), (2,3), (3,1),(3,3)\}. R ∗ = {( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 1 ) , ( 3 , 3 )} .