warshall算法

Warshall算法•有向图的传递闭包–一个n顶点有向图的传递闭包可以定义为一个n阶布尔矩阵T={tij}，如果顶点i到顶点j存在一条有效路径，则tij=1,否则tij=01Warshall算法思想•划分阶段–用n阶布尔矩阵R(k)(0≤k ≤n)来表示有向图中任意一对节点是否有有向路径的信息–因此，可将原问题划分为如下的决策阶段： R(0),…, R(k-1), R(k),…, R(n)2–具体来说，当且仅当，从节点i到节点j存在一条有向路径，且该路径上的每一个中间节点的编号都不大于k时，矩阵R(k)的第i行第j列的元素rij(k)=1vi，每个节点编号都不大于k的中间节点集，vj3•R（（0））就只是有向图的邻接矩阵就只是有向图的邻接矩阵 •R（（1））包含可以用第一个顶点作为中间点的包含可以用第一个顶点作为中间点的路径信息路径信息 •R（（n））说明可以用所有的顶点作为中间点寻说明可以用所有的顶点作为中间点寻找有向路径，所以找有向路径，所以R（（n））就是我们要求的传就是我们要求的传递闭包 •这个算法的中心是我们可以通过这个算法的中心是我们可以通过R（（k－－1））来来计算计算R（（k））的所有元素。

的所有元素45Warshall算法思想•确定递推关系式–对于路径： vi，每个节点编号都不大于k的中间节点集C，vj–情况1：Vk∈C，那么中间节点集合的节点编号定不会大于k-1，因此有： rij(k)=rij(k-1), Vk∈C–情况2： Vk∈C ，则有路径： vi，编号≤k-1的节点集，Vk，编号≤k-1的节点集， vj 此时节点i到节点j是否有路径，取决于两部分“编号≤k-1的节点集”，因此有： rij(k)=rik(k-1) 和 rkj(k-1) , Vk∈C56Warshall算法思想•递推关系式rij（（k））＝＝rij（（k－－1））or rik（（k－－1））and rik（（k－－1））67Warshall算法实例该矩阵反映了不包含中间顶点的路径，框起来的行和列用来计算R(1)该矩阵反映了包含编号不大于1的中间顶点（也就是a）的路径(有一条从d到b的新路径)框起来的行和列用来计算R (2)包含编号不大于2的中间顶点(也就是a,b)包含编号不大于3的中间顶点a,b,c)的路径，没有新路径包含编号不大于4的中间顶点(a,b,c,d)的路径.有五条新路径78Warshall算法算法 Warshall(A[1..n,1..n])//实现计算传递闭包的Warshall算法//输入：包括n个节点有向图的邻接矩阵//输出：该有向图的传递闭包R(0)Afor(k1;k<=n;k++) for(i1;i<=n;i++) for(j1;j<=n;j++) R(k)[i,j]R(k-1)[i,j] or R(k-1)[i,k] and R(k-1)[k,j]return R(n)8矩阵乘法的算法•void Mult_matrix( int c[][], int a[][], int b[][]， int n)　{　　　　// a、、b 和和 c 均为均为 n 阶方阵，且阶方阵，且 c 是是 a 和和 b 的的乘积乘积　　for (i=1; i<=n; ++i)　　　for (j=1; j<=n; ++j) {　　　　c[i,j] = 0;　　　　　for (k=1; k<=n; ++k)　　　　　c[i,j] += a[i,k]*b[k,j];　　　}　}// Mult_matrix•算法的时间复杂度为  (n3) 。