#include<stdio.h>
#include<conio.h>
#define inf 999
void main()
{
int i,j,k,n,w[20][20];
clrscr();
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();
}
Output:
Enter the no. of vertices : 5
Enter the weights : w[1][1]= 0
w[1][2]= 3
w[1][3]= 8
w[1][4]= 0
w[1][5]= 4
w[2][1]= 0
w[2][2]= 0
w[2][3]= 0
w[2][4]= 1
w[2][5]= 7
w[3][1]= 0
w[3][2]= 4
w[3][3]= 0
w[3][4]= 0
w[3][5]= 0
w[4][1]= 2
w[4][2]= 0
w[4][3]= 5
w[4][4]= 0
w[4][5]= 0
w[5][1]= 0
w[5][2]= 0
w[5][3]= 0
w[5][4]= 6
w[5][5]= 0
0 3 8 999 4
999 0 999 1 7
999 4 0 999 999
2 999 5 0 999
999 999 999 6 0
The resultant Matrix :
0 3 8 4 4
3 0 6 1 7
7 4 0 5 11
2 5 5 0 6
8 11 11 6 0
0 Comments