C Program to implement Floyd’s Algorithm


Levels of difficulty: / perform operation:

Floyd’s algorithm uses to find the least-expensive paths between all the vertices in a Graph.

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();
}