Solve All-Pairs Shortest Path Problem using Floyd–Warshall Algorithm



Program:



#include<stdio.h>
#include<conio.h>
#define inf 999

void main()
{
 int i,j,k,n,w[20][20];
 clrscr();
 printf("\n Enter the no. of vertices : ");
 scanf("%d",&n);
 printf("\n Enter the weights : ");
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      {
       printf("w[%d][%d]= ",i,j);
       scanf("%d",&w[i][j]);
    if(i!=j && (w[i][j]==0))
      w[i][j]=inf;
       }

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


       for(k=1;k<=n;k++)
 {
    for(i=1;i<=n;i++)
     {
       for(j=1;j<=n;j++)
        {
   if(w[i][k]+w[k][j]<w[i][j])
       w[i][j]=w[i][k]+w[k][j];
        }
     }
 }


  printf("\n The resultant Matrix : \n");
    for(i=1;i<=n;i++)
 {
     printf("\n");
     for(j=1;j<=n;j++)
        printf("%d\t",w[i][j]);
 }

 getch();

}






Output: 





 Enter the no. of vertices : 5

 Enter the weights : w[1][1]= 0
w[1][2]= 3
w[1][3]= 8
w[1][4]= 0
w[1][5]= 4
w[2][1]= 0
w[2][2]= 0
w[2][3]= 0
w[2][4]= 1
w[2][5]= 7
w[3][1]= 0
w[3][2]= 4
w[3][3]= 0
w[3][4]= 0
w[3][5]= 0
w[4][1]= 2
w[4][2]= 0
w[4][3]= 5
w[4][4]= 0
w[4][5]= 0
w[5][1]= 0
w[5][2]= 0
w[5][3]= 0
w[5][4]= 6
w[5][5]= 0

0       3       8       999     4
999     0       999     1       7
999     4       0       999     999
2       999     5       0       999
999     999     999     6       0
 The resultant Matrix :

0       3       8       4       4
3       0       6       1       7
7       4       0       5       11
2       5       5       0       6
8       11      11      6       0











Comments

Post a Comment

Popular posts from this blog

Write a Program to Add two 3x3 Matrix using C

Image
#include<stdio.h> void main () { int a [ 3 ][ 3 ], b [ 3 ][ 3 ], s [ 3 ][ 3 ], i , j ; printf ( "Enter the values of 1st matrix" ); for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { scanf ( "%d" , & a [ i ][ j ]); } } printf ( "Enter the values of 2nd matrix" ); for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { scanf ( "%d" , & b [ i ][ j ]); } } for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { s [ i ][ j ] = a [ i ][ j ] + b [ i ][ j ]; } } printf ( " \n The Sum is : \n " ); for ( i = 0 ; i < 3 ; i ++ ) { printf ( " \n\n " ); for ( j = 0 ; j < 3 ; j ++ ) { printf ( " \t %d" , s [ i ][ j ]); }
Read more

C program for Unit Conversion

Image
/* Convert Celsius to Fahrenheit */ #include<stdio.h> void main() {     float c,f;     printf("Enter the temperature in Celcius: ");     scanf("%f",&c);     f = c * 9/5 + 32;     printf("Temperature in Farenheit: %f",f); } /* Convert Farenheit to Celcius */ #include<stdio.h> void main() {     float c,f;     printf("Farenheit : ");     scanf("%f",&f);     c = (f - 32) * 5/9;     printf("Celcius: %f",c);  } /*Convert Meter to Feet*/ #include<stdio.h> void main() {     float m,f;     printf("Meter : ");     scanf("%f",&m);     f = 3.2808399 * m;     printf("Feet: %f",f); } /* Convert Feet to Meter */ #include<stdio.h> void main() {     float m,f;     printf("Feet : ");     scanf("%f",&f);     m = f / 3.2808399;     printf("Meter: %f",m); } /*Convert Km to M/cm/mm*/ #include<stdio.h> void main() {   float km;   char v;   float
Read more

Write a Program to Add two 5x5 Matrix using C

Image
#include<stdio.h> void main() {   int a[5][5],b[5][5],c[5][5];   int i,j;   for(i=0;i<5;i++)   {     printf("\nEnter elements of %d row of first Matrix: ",i+1);     for(j=0;j<5;j++)       scanf("%d",&a[i][j]);   }   for(i=0;i<5;i++)   {     printf("\nEnter elements of %d row of second Matrix: ",i+1);     for(j=0;j<5;j++)       scanf("%d",&b[i][j]);   }   printf("\nSum of Matrix:\n\n");   for(i=0;i<5;i++)   {     for(j=0;j<5;j++)     {       c[i][j]=a[i][j]+b[i][j];       printf("%3d ",c[i][j]);     }     printf("\n");   } }
Read more