All Pairs Shortest Path Using C programming

April 23, 2017

Given a directed, connected weighted graph

G (V, E)

, for each edge

⟨ u, v ⟩ \in E

, a weight

w (u, v)

is associated with the edge. The all pairs of shortest paths problem (APSP) is to find a shortest path from

u

v

for every pair of vertices

u

and

v

V

#include<conio.h>
#include<stdio.h>
int n,i,j,k,cost[10][10];
void apsp(int[10][10]);
int min(int,int);

void main()
{

// here we accept the cost matrix:
 printf("Enter the no of vertices: ");
 scanf("%d",&n);
 printf("Enter the cost adjacency matrix: ");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
  {
   scanf("%d",&cost[i][j]);
  }
 }


  apsp(cost);
 getch();
}

void apsp(int cost[10][10])
{

/*since we are finding various versions of the same adjacency matrix, we use a 3D matrix. The first dimension can be considered as the version no. of the matrix*/
 int A[5][10][10];


  for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
  {
   A[0][i][j] = cost[i][j];  // initializing the 0th version of A to the cost matrix
  }
 }
 
 for(k=1;k<=n;k++)
 {
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    A[k][i][j] = min(A[k-1][i][j],(A[k-1][i][k]+A[k-1][k][j]));
// the standard formula Ak(i,j) =   min(Ak-1(i,j),(Ak-1(i,k)+Ak-1(k,j)))
   }
  }
 }

 for(k=0;k<=n;k++)
 {
  printf("A(%d):\n",k);
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    printf("%d\t",A[k][i][j]); // printing all versions of the matrix A
   }
   printf("\n");
  }
 }
}
int min(int a,int b)
{
 if(a<b)
  return a;
 else return b;
}