All Pair Shortest Path Algorithm > C Program

Analysis of Algorithm

All Pair Shortest Path Algorithm > C Program

#include<stdio.h>
#include<conio.h>
int cost[10][10],a[10][10],i,k,j,c;
int min(int a,int b)
{

  if(a<b)
  return a;
  else
  return b;
}
void main()
{
// clrscr();
 int n,m;
 clrscr();
 printf("Enter the number of vertices:\n");
 scanf("%d",&n);
 printf("Enter the number of edges:\n");
 scanf("%d",&m);
printf("start end cost");
 for(k=1;k<=m;k++)
 {
  scanf("%d%d%d",&i,&j,&c);
  a[i][j]=cost[i][j]=c;
 }
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 {
  if(a[i][j]==0 && i!=j)
    a[i][j]=31999;
 }
 for(k=1;k<=n;k++)
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
 printf("The resultant Matrix is:\n");
 for(i=1;i<=n;i++)
 {
   for(j=1;j<=n;j++)
   {
     if(a[i][j]!=31999)
     printf("%d ",a[i][j]);
   }
   printf("\n");
 }
 getch();
}

/*
Enter the number of vertices:
3
Enter the number of edges:
5
start end cost
1 2 4
1 3 11
2 3 2
2 1 6
3 1 3
The resultant Matrix is:
0 4 6
5 0 2
3 7 0

*/