FLOYD'S ALGORITHM

Finding The Shortest Distance And Path Between Every Pair Of Vertices Using Floyd's Algorithm

Source code :-

#include<stdio.h>
#define maxsize 20
void disp_matrix(int [][maxsize],int );
void show_path(int [][maxsize],int ,int );
int main()
{
	int d[maxsize][maxsize],s[maxsize][maxsize],i,j,k,n;
	printf("Enter the number of vertex : ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)
			{
				d[i][j]=32767;
				s[i][j]=32767;
				continue;
			}
			printf("\nEnter weightage between [%d][%d] (if no edge then enter 32767) = ",i,j);        
			scanf("%d",&d[i][j]);
			s[i][j]=j;
		}
		printf("\n");
	}
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			if(i==k)
				continue;
			for(j=1;j<=n;j++)
			{
				if(j==k||i==j)
					continue;	
				if(d[i][k]+d[k][j]<d[i][j])
				{
					d[i][j]=d[i][k]+d[k][j];
					s[i][j]=k;
				}	
			}
		}
	}
	printf("\nThe Distance matrix is :-\n\n");
	disp_matrix(d,n);
	printf("\n\nThe Path matrix is :-\n\n");
	disp_matrix(s,n);
	printf("\nEnter the two vertex whose distance you want to know :-\n");
	printf("\nEnter the starting vertex Vi = ");
	scanf("%d",&i);
	printf("\nEnter the ending vertex Vj = ");
	scanf("%d",&j);
	if(i<1||i>n)
	{
		printf("\nThe starting vertex is not found.");
		return 1;
	}
	else if(j<1||j>n)
	{
		printf("\nThe ending vertex is not found.");
		return 1;
	}
	if(i==j)
	{
		printf("\nThe starting vertex and the ending vertex will not same.");
		return 1;
	}
	if(d[i][j]==32767)
	{
		printf("\nThere are no minimum distance between vertex %d to %d\n",i,j);
		printf("\nThere are no shortest path between vertex %d to %d",i,j);
		return 1;
	}
	printf("\nThe shortest distance between vertex %d to %d is = %d\n",i,j,d[i][j]);
	printf("\nThe shortest path from %d to %d is : ",i,j);
	printf("%d",i);
	show_path(s,i,j);	
	return 1;
}
void show_path(int s[][maxsize],int i,int j)
{
	if(s[i][j]==j)
	{
		printf(" -> %d",s[i][j]);
		return;
	}	
	show_path(s,i,s[i][j]);
	show_path(s,s[i][j],j);
}
void disp_matrix(int a[][maxsize],int n)
{
	int i,j;
	for(i=1;i<=n;i++)
	{	
		printf("| ");
		for(j=1;j<=n;j++)
 		{
		 	if(i==j)
		 		printf(" - ");
		 	else	
				printf("%2d ",a[i][j]);
   		}
   		printf("|\n");
	}
}

Input-Output :-

abhi@hp-15q-laptop:~$ gcc floyd.c
abhi@hp-15q-laptop:~$ ./a.out

Enter the number of vertex : 4

Enter weightage between [1][2] (if no edge then enter 32767) = 7

Enter weightage between [1][3] (if no edge then enter 32767) = 32767        

Enter weightage between [1][4] (if no edge then enter 32767) = 2


Enter weightage between [2][1] (if no edge then enter 32767) = 2

Enter weightage between [2][3] (if no edge then enter 32767) = 4

Enter weightage between [2][4] (if no edge then enter 32767) = 3


Enter weightage between [3][1] (if no edge then enter 32767) = 32767

Enter weightage between [3][2] (if no edge then enter 32767) = 32767

Enter weightage between [3][4] (if no edge then enter 32767) = 1


Enter weightage between [4][1] (if no edge then enter 32767) = 32767

Enter weightage between [4][2] (if no edge then enter 32767) = 3

Enter weightage between [4][3] (if no edge then enter 32767) = 32767


The Distance matrix is :-

|  -  5  9  2 |
|  2  -  4  3 |
|  6  4  -  1 |
|  5  3  7  - |


The Path matrix is :-

|  -  4  4  4 |
|  1  -  3  4 |
|  4  4  -  4 |
|  2  2  2  - |

Enter the two vertex whose distance you want to know :-

Enter the starting vertex Vi = 1

Enter the ending vertex Vj = 3

The shortest distance between vertex 1 to 3 is = 9

The shortest path from 1 to 3 is : 1 -> 4 -> 2 -> 3