Floyd warshall algorithm

// Floyd warshall algorithm.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"
using namespace std;

class path
{
       int n;
       int p[10][10];
       int a[10][10];
       int c[10][10];
public:
       void get();
       void pm();
       void ap();
       void disp();
};
void path::get()
{
       int i, j, k;
       cout << "Enter the no. of nodes in the graph:" << "\n";
       cin >> n;
       cout << "Enter the adjacency matrix:";
       for (i = 1; i <= n; i++)
       {
             for (j = 1; j <= n; j++)
                    cin >> a[i][i];
             p[i][j] = 0;
       }

cout << "Enter The cost matrix is :";
for (i = 1; i <= n; i++)
{
       for (j = 1; j <= n; j++)
       {
             cin >> c[i][j];
       }
}
for (i = 1; i <= n; i++)
{
       for (j = 1; j <= n; j++)
       {
             p[i][j] = a[i][j];
       }
}
}
   void path::disp()
   {
          cout<<"The output matrix for the given graph is :";
          for(int i = 1; i <= n; i++)
          {
                for (int j = 1; j <= n; j++)
                {
                       cout << p[i][j] << " ";
                }
                cout << endl;
          }
   }
  void path::pm()
   {
          int i, j, k;
          for (k = 1; k <= n; k++)
          {
                for (i = 1; i <= n; i++)
                {
                       for (j = 1; j <= n; j++)
                       {
                              p[i][j] = p[i][j] || p[i][k] && p[k][j];
                       }
                }
          }
   }
   void path::ap()
   {
          int i, j, k;
          for (i = 1; i <= n; i++)
          {
                for (j = 1; j <= n; j++)
                {
                       p[i][j] = c[i][j];
                }
          }
          for (k = 1; k <= n; k++)
          {
                for (i = 1; i <= n; i++)
                {
                       for (j = 1; j <= n; j++)
                       {
                              if (p[i][j]<p[i][k] + p[k][j])
                              {
                                     p[i][j] = p[i][j];
                              }
                              else
                              {
                                     p[i][j] = p[i][k] + p[k][j];
                              }
                       }
                }
          }
   }
   void main()
   {
          path p;
          p.get();
          p.pm();
          cout << "path matrix is :";
          p.disp();
          p.ap();
          cout << "all pair shortest path matrix is :";
          p.disp();
          system("pause");

   }



Share on Google Plus