Solve All-Pairs Shortest Path Problem using Floyd – Warshall Algorithm

#include<stdio.h>
#include<conio.h>
#define inf 999

void main()
{
 int i,j,k,n,w[20][20];
 printf("\n Enter the no. of vertices : ");
 scanf("%d",&n);
 printf("\n Enter the weights : ");
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      {
       printf("w[%d][%d]= ",i,j);
       scanf("%d",&w[i][j]);
    if(i!=j && (w[i][j]==0))
      w[i][j]=inf;
       }

 for(i=1;i<=n;i++)
 {
     printf("\n");
     for(j=1;j<=n;j++)
  printf("%d\t",w[i][j]);
 }


       for(k=1;k<=n;k++)
 {
    for(i=1;i<=n;i++)
     {
       for(j=1;j<=n;j++)
        {
   if(w[i][k]+w[k][j]<w[i][j])
       w[i][j]=w[i][k]+w[k][j];
        }
     }
 }


  printf("\n The resultant Matrix : \n");
    for(i=1;i<=n;i++)
 {
     printf("\n");
     for(j=1;j<=n;j++)
        printf("%d\t",w[i][j]);
 }

 getch();

}

Leave a Reply

Your email address will not be published. Required fields are marked *