回 帖 发 新 帖 刷新版面

主题:[讨论]用FLOYD算法实现带权无向图建立邻接矩阵的最短路径?

我在调用FLOYD函数的时候,遇到问题:如何打印所求最路径值?
void  floyd_short(Mgraph g,int u,int y)
{   int length[MAXVEX][MAXVEX]; //最短路径长度矩阵length                            
int i,j,s,k,t,next; 
int path[maxvex][maxvex];                                      
t=g.n;           //总顶点数                       
for(i=0;i<=t;i++)
for(j=0;j<=t;j++)
length[i][j]=g.arcs[i][j];                                   
if(u==y)
printf("the shortest road of the start-node and end-node is 0!");
if(u!=y)                    
for(i=0;i<=t;i++)
for(j=0;j<=t;j++)
{ path[i][j]=0; }
for(k=0;k<=t;k++)      //floyd算法求length矩阵  
for(i=0;i<=t;i++)
for(j=0;j<=t;j++)
           if(length[u][k]+length[k][y]<length[u][y])
{ length[u][y]=length[u][k]+length[k][y];
path[i][j]=k;}
next=path[i][j];
do{
next=path[next][j];
}while(next!=j);
if (length[i][j]==MAXINT)
printf(“无路径\n”);
//s=length[u][y];      //最短路径值                          
printf("the shortest road of the start-node and end-node is:%d\n",leng[u][y]);
}
那位朋友可以帮忙,谢谢你们了

回复列表 (共1个回复)

沙发

floyd算法求出来的最终的矩阵D[i][j],就是从i到j的最短路径,,,你问的应该是路径吧,路径可以用另外一个矩阵保存...好像你程序中也有...输出路径用递归,因为path[i][j]的值表示从i到j中间经过的结点,于是就可以:

void PrintPath(int i,int j)
{
  if(path[i][j]==-1)//直接连通,输出最短路径的时候,保证是连通的,-1为path的初值
    cout<<i;
  else
  {
    PrintPath(i,path[i][j]);
    PrintPath(path[i][j],j);
    cout<<j;
  }
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册