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();

}

   

0 Comments