用Floyd算法解决最短路径问题（动态规划）

系统管理员 2022-05-22 12:27 188阅读 0赞

求图的任两结点间的最短距离，采用动态规划原理的Floyd算法，算法具体解释见另一篇原创 https://blog.csdn.net/gnosed/article/details/78956449 ，还提到求一个顶点到其他顶点的Dijkstra算法。下面是一个例子，只输出了最短路径的值。

#include <stdio.h>
    #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( "\n" );
        }
    }
    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