Here the steps of Warshall’s Algorithm:
Step 1: Execute W:=MR,k:=0
Step 2: Execute k:=k+1
Step 3: For all i=k such that wik=1, and for all j execute the operation wij:=wij∨wkj
Step 4: If k=n, then stop: the solution is W=MR∗, else go to step 2.
In our case A={1,2,3,4,5,6} and R={(x,y) ∣ x−y=2}.
So n=6 and R={(3,1),(4,2),(5,3),(6,4)}.
W(0)=MR=⎣⎡001000000100000010000001000000000000⎦⎤
W(1)=⎣⎡001000000100000010000001000000000000⎦⎤
W(2)=⎣⎡001000000100000010000001000000000000⎦⎤
W(3)=⎣⎡001010000100000010000001000000000000⎦⎤
W(4)=⎣⎡001010000101000010000001000000000000⎦⎤
W(5)=⎣⎡001010000101000010000001000000000000⎦⎤
MR∗=W(6)=⎣⎡001010000101000010000001000000000000⎦⎤
R∗={(3,1),(4,2),(5,1),(5,3),(6,2),(6,4)}.
Comments
Leave a comment