FLOYD WARSHALL ALGORITHM

#include<stdio.h>
#include<stdlib.h>
#define MAX 10

void floyd(int);
int w[MAX][MAX], d[MAX][MAX][MAX];

void main()
{
int i, j,k,v;
clrscr();
printf("enter the no. of vertices\n");
scanf("%d",&v);
printf("enter the weights \n");

  for(i=1;i<=v;i++)
  {
   for(j=1;j<=v;j++)
    scanf("%d",&w[i][j]);
   }

 floyd(v);
 getch();
 }//end of main

 void floyd(int v)
 {
 int k, i,j;

  k=0;
for(i=1;i<=v;i++)
{
 for(j=1;j<=v;j++)
  d[k][i][j]=w[i][j];
 }

      for(k=1;k<=v;k++)
      {
       for(i=1;i<=v;i++)
    {
      for(j=1;j<=v;j++)
       d[k][i][j]=min(d[k-1][i][j], d[k-1][i][k]+ d[k-1][k][j]);
      }
    }

 //displayin matrix

 for(k=0;k<=v;k++)
 {
 printf(" k=%d \n",k);
   for(i=1;i<=v;i++)
   {
    printf("\n");
     for(j=1;j<=v;j++)
     printf("\t %d",d[k][i][j]);
    }
    printf("\n \n ");
  }
}

OUTPUT:

Enter the no. of vertices in the graph : 5

Enter the weight matrix :

0      3      8    1000    -4

1000   0    1000    1       7

1000   4      0    1000    1000

2     1000   -5     0      1000

1000  1000  1000    6       0

    k=0

     0       3       8       1000    -4

     1000    0       1000    1       7

     1000    4       0       1000    1000

     2       1000    -5      0       1000

     1000    1000    1000    6       0

     k=1

     0       3       8       1000    -4

     1000    0       1000    1       7

     1000    4       0       1000    996

     2       5       -5      0       -2

     1000    1000    1000    6       0

     k=2

     0       3       8       4       -4

     1000    0       1000    1       7

     1000    4       0       5       11

     2       5       -5      0       -2

     1000    1000    1000    6       0

     k=3

     0       3       8       4       -4

     1000    0       1000    1       7

     1000    4       0       5       11

     2       -1      -5      0       -2

     1000    1000    1000    6       0

     k=4

     0       3       -1      4       -4

     3       0       -4      1       -1

     7       4       0       5       3

     2       -1      -5      0       -2

     8       5       1       6       0

     k=5

     0       1       -3      2       -4

     3       0       -4      1       -1

     7       4       0       5       3

     2       -1      -5      0       -2

     8       5       1       6       0