首页 > 代码库 > 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