Auto AdSense

Sunday, 16 November 2014

Data Structures - Floyd warshall algorithm

   #include<iostream.h>
   #include<conio.h>
   #include<stdio.h>
   #include<stdlib.h>
   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;
     clrscr();
     cout<<"Enter the no. of nodes in the graph :";
     cin>>n;
     cout<<"Enter the adjacency matrix :";
     for(i=1;i<=n;i++)
     {
       for(j=1;j<=n;j++)
       {
         cin>>a[i][j];
         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();
     getch();
     p.ap();
     cout<<"all pair shortest path matrix is :";
     p.disp();
     getch();
   }      

No comments:

Post a Comment