原文来自离散数学结构课本, 作业是要翻译这段, 想着保留下来.
目前(17.05.15)只是将word上的复制过来而已, 日后有时间弄成标准的markdown形式
定理2:
A是一个基数为n的集合，R是A上的一个关系，则有
\(R ^ {\infty} = R \cup R^2 \cup R^3 \cup \cdots \cup R^n \).
换句话说，计算不需要用到R的n次以上的幂。
证明：
\(a,b\) 是 \(A\) 中的元素，假设是 \(R\) 中一条从 \(a\) 到 \(b\) 的路，那么都在 \(R\) 中。如果和是同一个顶点，约定 \(j>i\) ，那么这段路能被划分为三个部分。第一段从 \(a\) 到 \(x_i\) ，第二段从 \(x_i\) 到 \(x_j\) ，第三段从 \(x_j\) 到 \(b\) 。中间的第二段是个循环 ，因为 \(x_i = x_j\) ，所以我们除去重复然后连接前后两段。这样我们就得到一条更短的，从 \(a\) 到 \(b\) 的路。
现在 \(a,x_1,x_2,x_3,…,x_k,b\) 是 \(a\) 到 \(b\) 最短的路。如果 \(a \neq b\) ，那么 \(a,x_1,x_2,x_3,…,x_k,b\) 都是不同的顶点。否则，根据先前的讨论，我们能找到一条更短的路。因此，这条路的长度最多为 \(n-1\) （因为 \(\left| A\right| = n\) ）。如果 \(a = b\) ，相似地，顶点 \(a,x_1,x_2,x_3,…,x_k\) 是不同的，所以这条路的长度最多为 \(n\) 。总之，如果 \(a R^{\infty} b\) ，那么只要 \(a R^k b,1 \leq k \leq n\) 。因此 \(R ^ {\infty} = R \cup R^2 \cup R^3 \cup \cdots \cup R^n \).
例1用的方法都有明显的缺点。画图的方法对于巨大的集合不适用，它本身也不是系统化的方法。矩阵的方法是通用的且系统化得足以应用于计算机编程，但是对于庞大的矩阵，它就显得效率低下、过于浪费资源。幸运的是，有一个更加高效地计算传递闭包的算法。就是被熟知的沃夏尔算法，我们马上会讲到。
沃夏尔算法
设集合，是上的关系。如果是中的路，那么任意除了和都叫作路的内部点。现在，对于，我们用以下方法定义一个布尔矩阵。当到之间存在一条路，其内部点来自集合，那么的第i行第j列位置为1。
因为任意的顶点一定在集合中，它所代表的矩阵某个位置为1，当且仅当与之间有路。也就是说，。如果我们定义，那么我们就得到一个数列，。我们会展示怎么从计算得到。这样我们就能从一步一步，经过n步计算得到。这个过程被称为沃夏尔算法。和的幂级是不一样的，这种不同使得它能大量节省计算的传递闭包的步骤。
假设和。如果，就说明与有路，而且这条路只经过一些在集合的顶点。如果没有经过，那么肯定经过了集合中的点，即。如果经过了，那么情况就像图4.44所展示的那样。在定理2的证明中，我们假定了内部点都是互异的。因此只会在路中出现一次，所以子路1和子路2的点必然来自集合。这意味着和。
综上，只要
（1） 或者
（2）
这就是沃夏尔算法的基本内容。如果的i，j位置为1，根据（1），对应位置也为1。根据（2），如果的i，k位置为1，且k，j位置也为1，那么的i，j位置就为1。根据以下过程我们就能从计算出。
第一步 转移所有1到。
第二步 列出中第k行中为1的列数，第k列为1的行数
第三部 将中，位置设为1。
例二 思考定义在例一的关系R，那么
和n=4
第一步我们要计算那么。在2，1位置和1，2位置都为1，因此只是在基础上，在2，2位置变为1。
现在我们计算，那么，我们必须考虑第2列和第二行的位置。在位置1，2；2，2；2，1；2，3都为1。
因此，为了得到，我们必须在的基础上将1，1；1，2；1，3；2，1；2，2；2，3位置置为1。我们看到
继续这个过程，在位置1，3；2，3；3，4为1。为了得到，我们要将1，4；2，4置为1。那么
最后，第4列的1，2，3位置为1，不过没有1在第4行，所以没有新的位置被置为1，那么，我们就得到了例一的结果。
例二说明的过程产生了一下的算法CLOSURE来计算基于矩阵关系R的传递闭包。
算法 沃夏尔
这个算法是被建立在精确的执行出我们先前写出来的过程。如果稍作修改，它能稍微提高一点效率。如果我们认为赋值和比较是一步完成的，那么两个布尔矩阵A、B的布尔积需要步，因为我们要计算个元素，每个需要n次比较。去计算全部的积，我们需要步，因为需要步来计算矩阵乘积。如果直接用公式
会需要步来实现（忽略最终连接）。因此沃夏尔算法是对于直接用公式（1）计算的重大改进。