Warshall's algorithm

Algorithm

An algorithm is a finite sequence of precise step-by-step instructions.

Link to original

Warshall’s algorithm computes the matrix of the transitive closure $R^{\ast }$ of $R$. ?

• Given a relation $R$ on a set $A$ with $n$ elements, we begin with its $n\times n$ matrix. $\boxed{M_0}$
• There are $n$ rounds. For each, we mutate the matrix. $$M_0\stackrel{\text{round 1}}{⇝}{M}_1\stackrel{\text{round 2}}{⇝}{M}_2\stackrel{\text{round 3}}{⇝}...\stackrel{\text{round n}}{⇝}{M}_n$$ $\boxed{M_n}$ is the matrix of the transitive closure $R^{\ast }$ of $R$.
  • 1st rule: never change $1$ to $0$
  • 2nd rule: for the $k$ round, we select the $k$th row and the $k$th column, we look at all of the $0$ values not in this row or column. From the position of the $0$ value we are looking at, we check to see if the corresponding cells in the $k$th row and column are $1$, if they are, we change $0$ to $1$ otherwise we don’t do anything. $$\begin{array}{cc}& jk\text{th column}\\ \begin{array}{c}i\\ \\ k\text{th row}\end{array}& \left[\begin{array}{ccc}0& \to & 1\\ \downarrow & & \\ 1& & \end{array}\right]\end{array}\stackrel{\text{round }k}{⇝}\begin{array}{cc}& \begin{array}{ccc}j& & k\end{array}\\ \begin{array}{c}i\\ \\ k\end{array}& \left[\begin{array}{ccc}\text{1}& & 1\\ & & \\ 1& & \end{array}\right]\end{array}$$