Posted by : Naveen's Blogs Tuesday, 29 April 2014

  #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(); 
    }

Leave a Reply

Subscribe to Posts | Subscribe to Comments

Welcome to My Blog

Popular Post

Blogger templates

Powered by Blogger.

- Copyright © Data Structures using C++ -Robotic- Powered by Blogger - Designed by NAVEEN KUMAR -

6