离散数学中用warshall算法（由邻接矩阵计算可达矩阵）

Warshall算法是一种计算有向图可达矩阵的经典算法，它的基本思想是动态规划。假设 $A$ 是一个 $n\times n$ 的邻接矩阵，$R$ 是可达矩阵，$r_{i,j}$ 表示从顶点 $i$ 到顶点 $j$ 是否存在一条路径。Warshall算法的核心是以下递推式：

$$r_{i,j}=\begin{cases}
1, & i=j \text{ 或 } a_{i,j}=1 \\
r_{i,k}\land r_{k,j}, & \text{otherwise}
\end{cases}$$

其中，$\land$ 表示逻辑与运算。上述递推式表示，如果 $i=j$ 或者 $i$ 到 $j$ 有一条边，则 $r_{i,j}=1$；否则，$r_{i,j}$ 就等于 $i$ 到 $k$ 存在路径且 $k$ 到 $j$ 存在路径的逻辑与。

根据这个递推式，可以通过以下 Warshall 算法来计算可达矩阵：

for k from 1 to n do
    for i from 1 to n do
        for j from 1 to n do
            r_{i,j} = r_{i,j} or (r_{i,k} and r_{k,j})

其中，$\text{or}$ 表示逻辑或运算，$\text{and}$ 表示逻辑与运算。上述算法中的三重循环分别枚举 $k$、$i$、$j$，每次更新 $r_{i,j}$ 的值。算法的时间复杂度是 $O(n^3)$，空间复杂度是 $O(n^2)$。

Warshall算法在离散数学中应用广泛，可以用于计算有向图的可达性、传递闭包等问题。它的优点是实现简单、时间复杂度低，可以处理大规模的图。