弗洛伊德算法

  1. #include <stdio.h>
  2. #define MAXVEX 100
  3. #define INF 32767
  5. void Floyed(int cost[][MAXVEX],int n)
  6. {
  7.     int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
  8.     int i,j,k,pre;
  9.     for (i=0;i<n;i++)        /*置初值*/
  10.         for (j=0;j<n;j++) 
  11.         {    
  12.             A[i][j]=cost[i][j];
  13.             path[i][j]=-1;
  14.         }
  15.     for (k=0;k<n;k++)
  16.     {    
  17.         for (i=0;i<n;i++)
  18.             for (j=0;j<n;j++)
  19.                 if (A[i][j]>(A[i][k]+A[k][j])) 
  20.                 {    
  21.                     A[i][j]=A[i][k]+A[k][j];
  22.                     path[i][j]=k;
  23.                 }
  24.     }
  25.     printf("\n Floyed算法求解如下:\n"); 
  26.     for (i=0;i<n;i++)        /*输出最短路径*/
  27.         for (j=0;j<n;j++) 
  28.             if (i!=j)
  29.             {    
  30.                 printf("   %d->%d:",i,j);
  31.                 if (A[i][j]==INF)
  32.                 {    
  33.                     if (i!=j) 
  34.                         printf("不存在路径\n");
  35.                 }
  36.                 else 
  37.                 {    
  38.                     printf("路径长度为:%3d ",A[i][j]);
  39.                     printf("路径为%d ",i);
  40.                     pre=path[i][j];
  41.                     while (pre!=-1)
  42.                     {    
  43.                         printf("%d ",pre);
  44.                         pre=path[pre][j];
  45.                     }
  46.                     printf("%d\n",j);
  47.                 }
  48.             }
  49. }
  51. void main()
  52. {
  53.     int cost[6][MAXVEX]={        /*图6.9的代价矩阵*/
  54.         {0,50,10,INF,INF,INF},
  55.         {INF,0,15,50,10,INF},
  56.         {20,INF,0,15,INF,INF},
  57.         {INF,20,INF,0,35,INF},
  58.         {INF,INF,INF,30,0,INF},
  59.         {INF,INF,INF,3,INF,0}};
  60.     Floyed(cost,6);
  61.     printf("\n");
  62. }