WarShall算法

2024-10-01 01:53:19

1.引言

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

2.算法描述

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

\[R^{(0)},R^{(1)},\cdots，R^{(k)},\cdots ,R^{(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)}\)的计算方式如下：

\[R^{k}[i,j]\leftarrow R^{k-1}[i,j]+R^{k-1}[i,k]\cdot R^{k-1}[k,j]
\]

3.算法实现

for(int k=0;k<N;k++){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

            t[i][j]=t[i][j]||(t[i][k]&&t[k][j]);//由文中公式可得

        }

    }

}

算法优化

```
for(int k=0;k

参考资料：

离散数学（第三版），清华大学出版社

最新文章

热门文章