WarShall算法

1.引言

图的连通性问题是图论研究的重要问题之一，在实际中有着广泛的应用。例如在通信网络的联通问题中，运输路线的规划问题等等都涉及图的连通性。因此传递闭包的计算需要一个高效率的算法，一个著名的算法就是warshall在1962年提出的WarShall算法。

2.算法描述

使用n阶布尔矩阵\(R^{(k)}(0\leq k\leq n)\)来表示有向图中任意一对节点 是否含有路径的信息。因此，可将原问题划分为如下决策阶段：

具体来说，当且仅当从节点i到节点j存在一条有向路径，且该路径上的每一个中间节点的编号都不大于k时，矩阵\(R^{(k)}\)的第i行，第j列的元素\(r_{ij}^{(k)}=1\)。
对于\(R^{(k)}\)的计算我们可以由它的前趋\(R^{(k-1)}\) 计算得到（分级推进计算）。

• \(R^{(0)}\) ——该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的任意顶点出发的路径不含有中间顶点，此即邻接矩阵。
• \(R^{(1)}\) ——允许路径中包含第1个顶点（本例编号1）作为中间顶点。
• \(R^{(2)}\) ——允许路径中包含前2个顶点（本例编号1、2）作为中间顶点。
• \(R^{(k)}\) ——允许路径中包含前k个顶点作为中间顶点。
• \(R^{(n)}\) ——允许路径中包含全部 n 个顶点作为中间顶点。
  所以综上所述我们得到\(R^{(k)}\)的计算方式如下：

3.算法实现

for(int k=0;k