#include "stdio.h"
#define max  100
#define   n   3
void floyd(int rel[n][n],int a[n][n],int path[n][n])
{   int i,j,k;
     for(i=0;i<n;i++)
        for(j=0;j<n;j++)
                { if(i==j) path[i][j]=0;
                   else
                       {  if(rel[i][j]<max)
                                path[i][j]=i;
                           else  path[i][j]=0;

                       }
                   a[i][j]=rel[i][j];
                 }
      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])
                     {a[i][j]=a[i][k]+a[k][j];
                      path[i][j]=path[k][j];
                     }

}
main()
{    int rel[n][n]={ {0,2,6},
                     {18,0,8},
                     {3,4,0}
                    },a[n][n],path[n][n];
     int i,j;
     floyd(rel,a,path);
     for(i=0;i<n;i++)
        {for(j=0;j<n;j++)
              printf("%d   ",a[i][j]);
           printf("\n");
         }
      printf("\n");
      for(i=0;i<n;i++)
        {for(j=0;j<n;j++)
              printf("        %d",path[i][j]);
           printf("\n");
         }
     getch();

}