Floydアルゴリズム-すべての頂点間の最短パス(C++テンプレート)

15355 ワード


  
    
1 void Floyd( int * edge, int * path, const int order, const int maxNum)
2 {
3 int length;
4 if (path != NULL)
5 for ( int i = 0 ; i < order; i ++ )
6 for ( int j = 0 ; j < order; j ++ )
7 if (i != j && ( * (edge + order * i + j) < maxNum))
8 * (path + order * i + j) = i;
9 else
10 * (path + order * i + j) = 0 ;
11
12 for ( int k = 0 ; k < order; k ++ )
13 for ( int i = 0 ; i < order; i ++ )
14 for ( int j = 0 ; j < order; j ++ )
15 {
16 length = ( * (edge + i * order + k) + * (edge + k * order + j));
17 if (length < * (edge + i * order + j))
18 {
19 * (edge + i * order + j) = length;
20 if (path != NULL)
21 * (path + i * order + j) = * (path + k * order + j);
22 }
23 }
24 }

呼び出し例:

  
    
1 cosnt int MaxNum = 1000 ;
2 int a[ 4 ][ 4 ] = {{ 0 , 1 , MaxNum, 4 }, {MaxNum, 0 , 9 , 2 }, { 3 , 5 , 0 , 8 }, {MaxNum, MaxNum, 6 , 0 }};
3 int b[ 4 ][ 4 ];
4 Floyd(( int * )a, ( int * )b, 4 , MaxNum);