The All Pair Shortest Path Algorithm (Floyd-Warshall Algorithm)

Description: -

The all pair shortest path algorithm is also known as Floyd-Warshall algorithm is used to find all pair shortest path problem from a given weighted graph. As a result of this algorithm, it will generate a matrix, which will represent the minimum distance from any node to all other nodes in the graph.

 

At first the output matrix is same as given cost matrix of the graph. After that the output matrix will be updated with all vertices k as the intermediate vertex.

Algorithm: -

Begin
   for k := 0 to n, do
      for i := 0 to n, do
         for j := 0 to n, do
            if cost[i,k] + cost[k,j] < cost[i,j], then
               cost[i,j] := cost[i,k] + cost[k,j]
            done
         done
      done
      display the current cost matrix
End 

Program: -

#include<stdio.h>
#define INF 9999
int a[20][20];
void print(int n)
{
 int i,j;
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   if(a[i][j]<999)
    printf("%d    ",a[i][j]);
   else
    printf("INF  ");
   if(j==n-1)
    printf("\n");
  }
 }
}
void floyid_warsal(int n)
{
 int i,j,k;
 for(k=0;k<n;k++)
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    if(a[i][j]>a[i][k]+a[k][j])
     a[i][j]=a[i][k]+a[k][j];
}
int main()
{
 int n,i,j;
 printf("Enter the no of Nodes:"); scanf("%d",&n);
 printf("Enter Values:-\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   if(i==j)
    {
     a[i][j]=0;
    }
   else
   {
    printf("A(%d,%d)= ",i+1,j+1);
    scanf("%d",&a[i][j]);
   }
  }
 }
 printf("\nThe cost matrix of the graph:-\n");
 print(n);
 floyid_warsal(n);
 printf("\nMatrix of all pair shortest path:-\n");
 print(n);
 return 0;
}

Output: -

Enter the no of Nodes:4
Enter Values:-
A(1,2)= 4
A(1,3)= 8
A(1,4)= 999
A(2,1)= 999
A(2,3)= 5
A(2,4)= 12
A(3,1)= 999
A(3,2)= 999
A(3,4)= 7
A(4,1)= 5
A(4,2)= 999
A(4,3)= 999

The cost matrix of the graph:-
0    4    8    INF
INF  0    5    12
INF  INF  0    7
5    INF  INF  0

Matrix of all pair shortest path:-
0    4    8    15
17    0    5    12
12    16    0    7
5    9    13    0

Time-Complexity: -

 

The time complexity of this algorithm is O(V^3), here V is the number of vertices in the graph.