Floydアルゴリズムによる最短パス問題の解決(ダイナミックプランニング)

図の任意の2つのノード間の最短距離を求めて、動的な計画の原理のFloydアルゴリズムを採用して、アルゴリズムの具体的な解釈は別のオリジナルを参照してくださいhttps://blog.csdn.net/gnosed/article/details/78956449また,頂点を他の頂点に求めるDijkstraアルゴリズムについても言及した.次の例では、最短パスの値のみが出力されます.

#include 
#define Adjtype int
#define VN 10
#define MAX 99

struct GraphMatrix {
    Adjtype arc[VN][VN];
} pgraph;
struct Shortpath {
    Adjtype a[VN][VN];
    int nextvex[VN][VN];
} ppath;

void print( )
{
    for( int i = 0; i < VN; i++ ) {
        for( int j = 0; j < VN; j++ ) {
            printf("%d ",ppath.a[i][j]);
        }
        printf( "
" );
    }
}
void floyd( )
{
    for( int i = 0; i < VN; i++ ) //initialize
        for( int j = 0; j < VN; j++ ) {
            ppath.a[i][j] = pgraph.arc[i][j];
            if( pgraph.arc[i][j] != MAX )
                ppath.nextvex[i][j] = j;
            else
                ppath.nextvex[i][j] = -1;
        }
    for( int k = 0; k < VN; k++ ) //iterate calculate *ppath
        for( int i = 0; i < VN; i++ )
            for( int j = 0; j < VN; j++ ) {
                if( pgraph.arc[i][k] == MAX || pgraph.arc[k][j] == MAX )
                    continue;
                if( ppath.a[i][j] > pgraph.arc[i][k] + pgraph.arc[k][j] ) { //revise *ppath
                    ppath.a[i][j] = pgraph.arc[i][k] + pgraph.arc[k][j];
                    ppath.nextvex[i][j] = ppath.nextvex[i][k];
                }
            }
}

int main()
{
    for( int i = 0; i < VN; i++ )
        for( int j = 0; j < VN; j++ )
            scanf( "%d", &pgraph.arc[i][j] );
    floyd();
    print();
    return 0;
 } 

入力サンプル

0    99     8     7     6     5     4     3     2     1
99    0     99    8     7     6     5     4     3     2
8    99     0     99   8      7     6     5     4     3
7     8     99    0    99     8     7     6     5     4
6    7      8     99   0      99    8     7     6     5
5    6      7     8    99     0     99    8     7     6
4    5      6     7    8      99    0     99    8     7
3    4      5     6    7      8     99     0    99    8
2    3      4     5    6      7     8      99   0     99
1    2      3     4    5      6     7      8    99    0

出力サンプル

0 3 4 5 6 5 4 3 2 1
3 0 5 6 7 6 5 4 3 2
4 5 0 7 8 7 6 5 4 3
5 6 7 0 9 8 7 6 5 4
6 7 8 9 0 11 8 7 6 5
5 6 7 8 11 0 9 8 7 6
4 5 6 7 8 9 0 7 6 5
3 4 5 6 7 8 7 0 5 4
2 3 4 5 6 7 6 5 0 3
1 2 3 4 5 6 5 4 3 0