Floyd-Warshall Algorithm

Floyd Warshall Algorithm

The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed Graph.

This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative).

You will find working examples of Floyd-warshall algorithm in C and Python below.

Algorithm:

WARSHALL ALGORITHM

Example:

Input:

       graph[][] = { {0,   5,  INF, 10},

                    {INF,  0,  3,  INF},

                    {INF, INF, 0,   1},

                    {INF, INF, INF, 0} }

which represents the following graph

             10

       (0)------->(3)

        |                 /|\

      5|                  |

        |                  | 1

       \|/                 |

       (1)------->(2)

            3       

Note that the value of graph[i][j] is 0 if i is equal to j 

And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.

Output:

Shortest distance matrix

      0         5        8         9

    INF      0         3        4

    INF      INF     0        1

    INF      INF     INF    0 

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Program in C:

 #include <stdio.h>  
 #include <conio.h>  
   
 int A[10][10],graph[10][10];  
 void printMatrix(int nV);  
 void floydWarshall(int nV)  
 {  
  int i, j, k;  
  for (i = 0; i < nV; i++)  
  {  
   for (j = 0; j < nV; j++)  
    {    
     A[i][j] = graph[i][j];  
    }  
  }  
  printf("D^0\n");  
  printMatrix(nV);  
  for (k = 0; k < nV; k++)  
  {  
   for (i = 0; i < nV; i++)  
   {  
    for (j = 0; j < nV; j++)  
    {  
           if (A[i][k] + A[k][j] < A[i][j])  
             A[i][j] = A[i][k] + A[k][j];
    }  
   }  
   printf("D^%d\n",k+1);  
   printMatrix(nV);  
   printf("\n");  
  }  
  printf("All Pair Shortest Path:\n");  
  printMatrix(nV);  
 }  
 void printMatrix(int nV)  
 {   
  int i,j;  
  for (i = 0; i < nV; i++)  
  {  
   for (j = 0; j < nV; j++)  
   {  
    if (A[i][j] == 999)  
        printf("%4s", "INF");  
    else  
        printf("%4d", A[i][j]);  
   }  
   printf("\n");  
  }  
 }  
   
 int main()  
 {  
  int nV,i,j,n,e,u,v,w;  
  printf("enter the no of vertices");  
  scanf("%d",&nV);  
  printf("enter the number of edges");  
  scanf("%d",&e);  
  for(i=0;i<nV;i++)  
  {  
   for(j=0;j<nV;j++)  
   {  
    if(i==j)  
    {  
     graph[i][j]=0;  
       }  
    else  
    {  
     graph[i][j]=999;  
    }  
   }  
  }  
  printf("enter the weights \n");  
  for(i=1;i<=e;i++)  
  {  
   printf("enter u, v & w ");  
   scanf("%d %d %d \n",&u,&v,&w);  
   graph[u][v]=w;  
   //graph[v][u]=w;  
  }  
  floydWarshall(nV);  
  getch();  
  return 0;  
 }