Program to implement all pairs shortest path

Objective: C program to find all pairs shortest path using Floyd’s algorithm

Concept: Floyd’s algorithm is applicable to both directed and undirected graphs provided that they do not contain a cycle. It is convenient to record the lengths of shortest path in an n- by- n matrix D called the distance matrix. The element dij in the ith row and jth column of matrix indicates the shortest path from the ith vertex to jth vertex (1<=i, j<=n). The element in the ith row and jth column of the current matrix D(k-1) is replaced by the sum of elements in the same row i and kth column and in the same column j and the kth column if and only if the latter sum is smaller than its current value.

Algorithm Floyd(W[1..n,1..n])
//Implements Floyd’s algorithm for the all-pairs shortest paths problem
//Input: The weight matrix W of a graph
//Output: The distance matrix of shortest paths length
{
D ← W
for k←1 to n do
{
for i ← 1 to n do
{
for j ← 1 to n do
{
D[i,j] ← min (D[i, j], D[i, k]+D[k, j] )
}
}
}
return D
}

				
					#include<stdio.h> 
#include<conio.h> 
void floyd(int[10][10],int); 
int min(int,int); 
void main() 
{ 
int n,a[10][10],i,j; 
printf("Enter the no.of nodes : "); 
scanf("%d",&n); 
printf("\nEnter the cost adjacency matrix\n"); 
for(i=1;i<=n;i++) 
for(j=1;j<=n;j++) 
scanf("%d",&a[i][j]); 
floyd(a,n); getch(); 
}
void floyd(int a[10][10],int n) 
{
int d[10][10],i,j,k; 
for(i=1;i<=n;i++) 
{ 
for(j=1;j<=n;j++)
d[i][j]=a[i][j]; 
} 
for(k=1;k<=n;k++) 
{
for(i=1;i<=n;i++) 
{
for(j=1;j<=n;j++) 
{
d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 
} 
} 
}
printf("\nThe distance matrix is\n"); 
for(i=1;i<=n;i++) 
{ 
for(j=1;j<=n;j++) 
{ 
printf("%d\t",d[i][j]); 
} 
printf("\n"); 
} 
} 
int min (int a,int b) 
{
if(a<b) 
return a; 
else 
return b; 
}

Leave a Reply