Thursday, 1 May 2014

All Pair Shortest Path C Program

/*ALL PAIR SHORTEST PATH*/
#include<conio.h>
#include<stdio.h>
void main()
{
   int wt[10][10],n,i,j;
   void Floyd_shortest_path(int matrix[10][10],int n);
   clrscr();
   printf("\n Create a graph using Adjacency Matrix");
   printf("\n\n How many vertices are there ?");
   scanf("%d",&n);
   printf("\nEnter The Elements");
   printf("[Enter 999 as infinity value]");
   for(i=1;i<=n;i++)
   {
    for(j=1;j<=n;j++)
    {
      printf("\nwt[%d][%d]",i,j);
      scanf("%d",&wt[i][j]);
    }
   }
   printf("\n\tComputing All pair shortest path...\n");
   Floyd_shortest_path(wt,n);
   getch();
}
void Floyd_shortest_path(int wt[10][10],int n)
{
   int D[5][10][10],i,j,k;
   int min(int,int);
    for(i=1;i<=n;i++)
   {
    for(j=1;j<=n;j++)
    {
      D[0][i][j]=wt[i][j];
    }
   }
   for(k=1;k<=n;k++)
   {
      for(i=1;i<=n;i++)
     {
       for(j=1;j<=n;j++)
      {
D[k][i][j]=min(D[k-1][i][j],(D[k-1][i][k]+D[k-1][k][j]));
      }
     }
   }
   for(k=1;k<=n;k++)
   {
      printf("\nD(%d)=\n",k);
      for(i=1;i<=n;i++)
     {
      for(j=1;j<=n;j++)
      {
printf("%d\t",D[k][i][j]);
      }
    printf("\n");
   }
  }
}
  int min(int a,int b)
  {
    if(a<b)
    return a;
    else
    return b;
  }
OUTPUT:

 Create a graph using Adjacency Matrix

 How many vertices are there ?4

Enter The Elements[Enter 999 as infinity value]
wt[1][1]0

wt[1][2]999

wt[1][3]3

wt[1][4]999

wt[2][1]2

wt[2][2]0

wt[2][3]999

wt[2][4]999

wt[3][1]999

wt[3][2]7

wt[3][3]0

wt[3][4]1

wt[4][1]6

wt[4][2]999

wt[4][3]999

wt[4][4]0

        Computing All pair shortest path...

D(1)=
0       999     3       999
2       0       5       999
999     7       0       1
6       999     9       0

D(2)=
0       999     3       999
2       0       5       999
9       7       0       1
6       999     9       0

D(3)=
0       10      3       4
2       0       5       6
9       7       0       1
6       16      9       0

D(4)=
0       10      3       4
2       0       5       6
7       7       0       1
6       16      9       0

No comments:

Post a Comment