首页 > 代码库 > Warshall算法
Warshall算法
---用Warshall算法解决传递闭包问题
---在一个关系R中,如果任意的(a,b)和(b,c)在关系R中,则(a,c)也一定在关系R中,则称R是可传递的。一个关系R的传递闭包是包
含R的最小的传递关系。
---Warshall算法不用来计算最短路径,而是用来判断i和j之间是否单向连接,无论是直接连接还是间接连接
---初始条件不再是邻接矩阵,而是关系矩阵,如果两个点之间直接单向连接,那么在矩阵中对应的值就为1,反之为0
---根据已有的直接连接关系得出其它所有的间接连接关系,即判断两点之间是否相连,是直接相连还是间接相连
---初始条件为关系矩阵,递推关系为:
A(k)ij = A(k-1)ij 并 ( A(k-1)ik 交 A(k-1)kj )
A(k-1)ij 的意思是说不再在中间加入中间点k,如果在不加入k的情况下它就是连接的,那么结果就是连接,反之就加入中间点
k,只有从i到k,再从k到j二者都必须满足连接时,ij之间才是连接的。
---伪代码描述
Input: 关系矩阵A
Output: 关系矩阵A
foo(A){
n = A.last;
for k=1 to n
for i=1 to n
for j=1 to n
A[i][j] = A[i][j] 并 (A[i][k] 交 A[k][j])
}
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | <span style= "font-family: courier new,courier; font-size: 14px;" > public class Demo { public static void foo( int [][] A) { int n = A. length; for ( int k = 0 ; k < n; k++) { for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { A[i][j] = A[i][j]|(A[i][k]&A[k][j]); } } } } public static void print( int [][] A){ for ( int i = 0 ; i < A. length; i++) { for ( int j = 0 ; j < A. length; j++) { System. out. print(A[i][j]+ "\t" ); } System. out.println(); } } public static void main(String[] args) { int [][] A = { { 0 , 1 , 0 , 0 , 0 }, { 0 , 0 , 1 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 1 }, { 0 , 0 , 0 , 1 , 1 } }; System. out.println( "最初的关系矩阵:" ); print(A); foo(A); System. out.println( "结果矩阵:" ); print(A); } } </span> |
结果:
最初的关系矩阵:
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 1 1
结果矩阵:
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。