最短路径--弗洛依德算法.txt

数据结构C对图的操作算法

void shortpath_FLOYD(int cost[][M],int path[][M],int length[][M],int n)//cost是图的邻接矩阵存储方式
{  int i,j,k,wm;  //path[i][j]存储从Vi到Vj的最短路径上Vj前一顶点序号；length[][]存放最短路径长度

   for(i=0;i<n;i++)
     for(j=0;j<n;j++)
     {  length[i][j]=cost[i][j];
        if (i==j)  path[i][j]=0; //对角线全为0
        else if(length[i][j]<MAX) //MAX表示无穷大
            path[i][j]=i+1;
        else  path[i][j]=0; //i,j不连通，即length[i][j]无穷大，则j无前顶点，用0表示
     }//赋初值结束，准备工作完成

   for(k=0;k<n;k++)//添加n个顶点，逐个试探
     for(i=0;i<n;i++)
       for(j=0;j<n;j++) //矩阵的行列坐标i,j
         if(length[i][k]+length[k][j]<length[i][j])
         {  length[i][j]=length[i][k]+length[k][j];
            path[i][j]=path[k][j]; //存储Vi到Vj的最短路径上Vj前一顶点序号
         }
}