Implement all pair shortest path problem using Floyd’s algorithm. code example

Example 1: all pair shortest path algorithm in c with program

/* ALL PAIR SHORTEST PATH */

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>

int c[100][100], p[100][100];  //c-cost matrix, p-path matrix(to store the path)
int inf=1000, v;     //Assume Infinity as 1000
//int min(int x, int y);
void show();
void path(int, int);

int main()
{
 int i, j, k, x;
 clrscr();

 printf("Enter the number of vertices in the graph: ");
 scanf("%d", &v);

/*
 for(i=1;i<=v;i++)
  for(j=1;j<=v;j++)
   if(i==j)
    c[i][j]=0;
   else
   {
    printf("Is %d connected to %d?",i,j);
    printf("If yes, enter weight, else enter %d: ",inf);
    scanf("%d", &c[i][j]);
   }
*/

 printf("\nEnter adjacency matrix:\n");
 printf("(Enter 1000 if there is no path)\n");
 for(i=1;i<=v;i++)
  for(j=1;j<=v;j++)
  {
   scanf("%d", &c[i][j]);
   p[i][j]=-1;
  }

 printf("\n");

 for(k=1;k<=v;k++)
 {
  for(i=1;i<=v;i++)
  {
   for(j=1;j<=v;j++)
   {
    if(i==j)
     c[i][j]=0;
    else
    {
     x=c[i][k]+c[k][j];
     if(c[i][j]>x)
     {
      c[i][j]=x;
      p[i][j]=k;
     }
    }
   }
  }
  show();
  printf("\n");
 }

 printf("From\tTo\tPath\t\tTotal Min. Cost\n");
 for(i=1;i<=v;i++)
 {
  for(j=1;j<=v;j++)
  {
   if(i!=j)
   {
    printf("%d\t", i);
    printf("%d\t", j);

//    printf("Path from %d to %d is: ",i,j);
    printf("%d", i);
    path(i,j);
    printf("%d", j);

    printf("\t\t%d", c[i][j]);
    printf("\n");
   }
  }
 }
 getch();
 return 0;
}

//-------TO SHOW THE PASSES-------
void show()
{
 int i,j;
 for(i=1;i<=v;i++)
 {
  for(j=1;j<=v;j++)
   if(c[i][j]==1000)
    printf("INF\t");
   else
    printf("%d\t", c[i][j]);
  printf("\n");
 }
}

//-------TO SHOW THE PATH-------
void path(int i, int j)
{
 int k;

 k=p[i][j];
 if(k==-1)
 {
  printf("->");
  return;
 }
 path(i, k);
 printf("%d",k);
 path(k,j);
}

/* OUTPUT

Enter the number of vertices in the graph: 3

Enter adjacency matrix:
(Enter 1000 if there is no path)
0 8 5
3 0 1000
1000 2 0

0       8       5
3       0       8
INF     2       0

0       8       5
3       0       8
5       2       0

0       7       5
3       0       8
5       2       0

From    To      Path            Total Min. Cost
1       2       1->3->2         7
1       3       1->3            5
2       1       2->1            3
2       3       2->1->3         8
3       1       3->2->1         5
3       2       3->2            2
*/

Example 2: floyd warshall algorithm c program

#include<stdio.h>#include<conio.h>int min(int,int);void floyds(int p[10][10],int n) {	int i,j,k;	for (k=1;k<=n;k++)	  for (i=1;i<=n;i++)	   for (j=1;j<=n;j++)	    if(i==j)	     p[i][j]=0; else	     p[i][j]=min(p[i][j],p[i][k]+p[k][j]);}int min(int a,int b) {	if(a<b)	  return(a); else	  return(b);}void main() {	int p[10][10],w,n,e,u,v,i,j;	;	clrscr();	printf("\n Enter the number of vertices:");	scanf("%d",&n);	printf("\n Enter the number of edges:\n");	scanf("%d",&e);	for (i=1;i<=n;i++) {		for (j=1;j<=n;j++)		   p[i][j]=999;	}	for (i=1;i<=e;i++) {		printf("\n Enter the end vertices of edge%d with its weight \n",i);		scanf("%d%d%d",&u,&v,&w);		p[u][v]=w;	}	printf("\n Matrix of input data:\n");	for (i=1;i<=n;i++) {		for (j=1;j<=n;j++)		   printf("%d \t",p[i][j]);		printf("\n");	}	floyds(p,n);	printf("\n Transitive closure:\n");	for (i=1;i<=n;i++) {		for (j=1;j<=n;j++)		   printf("%d \t",p[i][j]);		printf("\n");	}	printf("\n The shortest paths are:\n");	for (i=1;i<=n;i++)	  for (j=1;j<=n;j++) {		if(i!=j)		    printf("\n <%d,%d>=%d",i,j,p[i][j]);	}	getch();}