code3[1].txt

此文件为数据结构用floyd算法实现最短路径的算法

二、  实验内容

假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。

算法思想：下面是R、W、Floyd求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用来进行n次迭代，矩阵P用来记录路径，P[i][j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点。

算法实现：
typedef  struct  node
{  int  no;
  float  wgt;
  struct  node  *next;
}edgenode;
typedef  struct
{  char  vtx;
   edgenode  *link;
   }vexnode;
                   typedef  vexnode  Graph[n];

void  Floyd(Graph G, float A[n][n], int p[n][n])
{
   int  i,  j,   k;
   for  (i=0; i<n; i++)
     for(j=0;j<n;j++)
  {
     A[i][j]=G[i][j];
     P[i][j]=-1;
     }
  for  (k=0; k<n; k++)
    for (i=0; i<n;  i++)
      for (j=0; j<n; j++)
       if(A[i][k] +A[k][j]<A[i][j])
          {
            P[i][j]=k;
           A[i][j]=A[i][k]+A[k][j];
           }
        }