Floyd算法思想

1个回答

  • 算法描述:

    (1) 用数组dis[i][j]来记录i,j之间的最短距离.初始化dis[i][j],若i=j则dis[i][j]=0,

    若i,j之间有边连接则dis[i][j]的值为该边的权值,否则dis[i][j]的值为 .

    (2) 对所有的k值从1到n,修正任意两点之间的最短距离,计算dis[i][k]+dis[k][j]的值,

    若小于dis[i][j],则dis[i][j]= dis[i][k]+dis[k][j],否则dis[i][j]的值不变.

    程序:

    void Floyd(int dis[n+1][n+1],int path[n+1][n+1],int n)

    {

    x09int i,j,k;

    x09for(k=1;k