warshallアルゴリズム

伝達関係閉包アルゴリズム
まず,関係集合を0,1行列に変換し,関係演算を容易にする.
一般的なアルゴリズムでは,行列点乗による反復により伝達関係閉パケットの集合が得られる.
コードは次のとおりです.

typedef struct matrix{//      
    int n;
    int a[10][10];
}Matrix;

Matrix getTranstiveClosure(Matrix matrixA,int matrix_n){
    for(int num=1;num//R^n,  n-1   C  ，0         
        for(int i=0;i//         
            for(int j=0;j){
                for(int k=0;k){
                    if(matrixA.a[i][j]==0)//     
                    matrixA.a[i][j]=(matrixA.a[i][k]&matrixA.a[k][j]);
                }
            }
        }
    }
    return matrixA;
}//M=getTranstiveClosure(matrixA);         

ここで,マトリクス点乗のアルゴリズム複雑度はO(n^3),反復回数はn−1回(R^nを結果として得た),アルゴリズム複雑度はO(n^4)であった.
このようなアルゴリズムでは,ある関係(a,b)を見つけるために,他の要素を中間要素として伝達関係があるか否かを判断することを特徴とする.
例えば,a,b,c,d,eはA集合に属し,RはAの関係集合であり,(a,b)を見つけるためには,c,d,eを中間要素として仮定(a,c)(c,b)∈R,
(a,c)(c,b)->(a,b)∈Rで伝達関係を得る.簡単に言えば、求めた関係に対して、中間要素の関係を遍歴して判断する.
 
warshallアルゴリズムを見てみましょう.
コードは次のとおりです.

Matrix warshall(Matrix matrixB,int matrix_n){
    for(int k=0;k//K                   
        for(int i=0;i//     
            for(int j=0;j){
                if(matrixB.a[i][j]==0){//     
                    matrixB.a[i][j]=matrixB.a[i][k]&matrixB.a[k][j];
                }// (a->b)&(b->c)-->(a->c)   
            }
        }
    }
}

warshallアルゴリズムのアルゴリズム複雑度はO(n^3)であり,行列の反復を必要とせず,中間要素を固定することによって関係を判断し,中間要素を逐次遍歴することが巧みである.
伝達関係を反復し,遍歴を必要とする中間要素をn個,求めた行列遍歴動作をn^2とし,n規模が十分大きい場合にwarshallアルゴリズムが優位性を体現できる.
まとめてみると,同じマトリクス上の求めた関係の要素に対して,一般的なアルゴリズムで必要とされる動作はn*(n−1)であり,warshallアルゴリズムではn回しか必要としない!
warshall例:同様にa,b,c,d,e∈Aに対して,関係集合R,(a,b)(b,c)(c,d)(d,e)∈Rは,まずaを中間要素とし,関係集合は変化せず,
更にb,多くなった(a,c)∈R,更にc,(a,d),更にd,(a,e).アルゴリズムは、開始時にルート開始点が決定されるため、中間要素の遍歴順序とは関係ありません.遍歴要素は伝達関係のみを決定します.