Implement All Pair Shortest Algorithm


#include<stdio.h>
#include<conio.h>
int cost[20][20],n,a[20][20];
void setdata();
void getdata();
void path();
void setdata()
{
int i,j,k;
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter cost matrix(32767 for infinity):");
for(i=1;i<=n;i++)
{
printf("\nEnter %d row\n",i);
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
}
}
}
void getdata()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d",a[i][j]);
printf("\n");
}
}
}
void path()
{
int i,j,k,l;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=cost[i][j];

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
l=a[i][k]+a[k][j];
a[i][j]=(a[i][j]>l)?l:a[i][j];
}
}
void main()
{
clrscr();
setdata();
path();
printf("\nMatrix with shortest path is:");
getdata();
getch();
}


Output:
Enter the number of nodes:3
Enter cost matrix(32767 for infinity):
Enter 1 row
0 4 11
Enter 2 row
602
Enter 3 row
370
Matrix with shortest path is:0
4
6
5
0
2
3
7
0

Previous Post Next Post