• 弗洛伊德算法

    弗洛伊德算法

    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. }