Tuesday, 6 June 2017

Implementation of Floyd Warshall Algorithm - C++

Floyd Warshall algorithm is used to find the shortest distance between the every pair of vertices in a given weight directed graph which does not contain any cycles of negative length ( The total length of any cycle in the graph should not be negative). The idea is very simple we  will pick all the vertices one by one and include the picked vertex between two every other pair of vertices as an intermediate vertex and update the distance matrix if the distance between the two vertex becomes smaller than before. Implementation of Floyd Warshall algorithm is very simple which is its main advantage. Implementation of Floyd Warshall algorithm in C++ is given below.


Algorithm


step 1:    Initialize Distance matrix i.e.   D(i,j) = adjacency(i,j)
step 2:    do For  k=1 to k=n:
step 3:              do For i=1 to i=n:
step 4:                       do For j=1 to j=n:
step 5:                               if    D[i][k]+D[k][j] < D[i][j]:
step 6:                                      set   D[i][j] = D[i][k]+D[k][j]
step 7:    Exit.




Example: 

                     

The implementation of the floyd warshall algorithm for the above example and its output is given below

Note:  1000 here representing infinity i.e there is not edge between those two vertex.

PROGRAM:

#include <iostream>
#include <stdio.h>
using namespace std;

class graph
{
   int adjacency[10][10],distance[10][10],n,i,j,k;
   public:
        void get_data();
        void floydwarshall();
        void print();
};

void graph::get_data()
{
  printf("\nEnter the total number of vertices: ");
  scanf("%d",&n);
  printf("\nEnter the adjacency matrix (If there is no \nedge betweent two vertex then enter 1000): \n\n");
  for(i=1;i<=n;i++)
  {
       for(j=1;j<=n;j++)
       {
             scanf("%d",&adjacency[i][j]);
       }
  }
}

void graph::floydwarshall()
{
 
   for(i=1;i<=n;i++)
   {
        for(j=1;j<=n;j++)
        {
             distance[i][j]=adjacency[i][j];
        }
   }

   /* Updating distance matrix by taking intermediate vertex 'k'
      between every other vertices pair */

   for(k=1;k<=n;k++)
   {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(distance[i][k]+distance[k][j]<distance[i][j])
                {
                      distance[i][j]=distance[i][k]+distance[k][j];
                }
            }
        }
   }
}
void graph::print()
{
 
  printf("\n\nThe final distance matrix is: \n\n");
  for(i=1;i<=n;i++)
  {
      for(j=1;j<=n;j++)
      {
          printf("%d\t\t",distance[i][j]);
      }
      printf("\n");
  }
}

int main()
{
  graph graph;
  graph.get_data();
  graph.floydwarshall();
  graph.print();
  return 0;
}


OUTPUT:



EmoticonEmoticon