# 求传递闭包的 Warshall 算法详解

## 过程详情

【例子】关系的矩阵是：

$$\boldsymbol{W}_{0}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right]$$

【分析与解答】

$\pmatrix{\color{red}0\\1\\1\\0}$ $a_{11}=0$ 跳过。

$\pmatrix{0\\\color{blue}1\\1\\0}$ $a_{\color{green}2\color{red}1}=1$，则 $a_{\color{red}1}$ 行加到 $a_{\color{green}2}$ 行：

$$\boldsymbol{W}=\left[\begin{array}{llll} \color{blue}0 & \color{blue}0 & \color{blue}0 & \color{blue}1 \\ 1+\color{blue}0 & 0+\color{blue}0 & 1+\color{blue}0 & 0+\color{blue}1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right]$$

$$\boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right]$$

$\pmatrix{0\\1\\\color{blue}1\\0}$，$a_{31} = 1$，则 $a_1$ 行加到 $a_3$ 行，得到：

$$\boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right]$$

$\pmatrix{0\\1\\1\\\color{red}0}$，$a_{41} = 0$，跳过。

$$\boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right]$$

$$\boldsymbol{W}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]$$

$$\boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]$$ $$\boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]$$ $$\boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]$$ $$\boldsymbol{W}=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]$$

## 例题

【例子】计算传递闭包之于：

$$\boldsymbol{A}= \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \end{bmatrix}$$

【分析与解答】

$(4,1) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{bmatrix}$$

$(1,2) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{bmatrix}$$

$(4,2) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

$(4,3) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

$(1,4) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

$(2,4) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

$(4,4) = 1$，故：

$$\boldsymbol{T}= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

🦔最终解。