Implementation of Floyd Warshall in C++ Using STL

1:  //   Floyd_Warshall.cpp  
2:  //     
3:  //   Copyright 2010 ananya <ananya@ananya-laptop>  
4:  //     
5:  //   This program is free software; you can redistribute it and/or modify  
6:  //   it under the terms of the GNU General Public License as published by  
7:  //   the Free Software Foundation; either version 2 of the License, or  
8:  //   (at your option) any later version.  
9:  //     
10:  //   This program is distributed in the hope that it will be useful,  
11:  //   but WITHOUT ANY WARRANTY; without even the implied warranty of  
12:  //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the  
13:  //   GNU General Public License for more details.  
14:  //     
15:  //   You should have received a copy of the GNU General Public License  
16:  //   along with this program; if not, write to the Free Software  
17:  //   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,  
18:  //   MA 02110-1301, USA.  
19:  #include <iostream>  
20:  #include <vector>  
21:  #include <stdio.h>  
22:  using namespace std;  
23:  int path(int x,int y,vector<vector<int> > & par)  
24:  {  
25:       if(x!=y)  
26:       {  
27:            path(x,par[x][y],par);  
28:            cout<<"-->"<<y;  
29:       }  
30:       return 0;  
31:  }  
32:  int main(int argc, char** argv)  
33:  {  
34:       int n;  
35:       cout<<"Enter the Number of nodes : ";  
36:       cin>>n;  
37:       vector<vector<int> > g(n+1,vector<int> (n+1));  
38:       vector<vector<int> > d(n+1,vector<int> (n+1));  
39:       vector<vector<int> > p(n+1,vector<int> (n+1));  
40:  /*     vector<vector<int> > Temp(n,vector<int> (n));  
41:       vector<vector<int> > pTemp((n,vecor<int> (n));  
42:  */       
43:       cout<<"use 3000 for INFINITY"<<endl;  
44:       cout<<"Enter the graph discription in row-major fashion:"<<endl;  
45:       for(int i=1;i<n+1;i++)  
46:            {  
47:                 for(int j=1;j<n+1;j++)  
48:                      {  
49:                           cin>>g[i][j];  
50:                      }  
51:            }  
52:       for(int i=1;i<n+1;i++)  
53:            {  
54:                 for(int j=1;j<n+1;j++)  
55:                      {  
56:                           d[i][j]=g[i][j];  
57:                           if(g[i][j]==0 || g[i][j]==3000)  
58:                                p[i][j]=0;  
59:                           else   
60:                                p[i][j]=i;  
61:                      }  
62:            }  
63:       for(int k=1;k<n+1;k++)  
64:       {  
65:            for(int i=1;i<n+1;i++)  
66:                 {  
67:                      for(int j=1;j<n+1;j++)  
68:                      {  
69:                           if(d[i][j] > d[i][k]+d[k][j])  
70:                           {  
71:                                d[i][j]=d[i][k]+d[k][j];  
72:                                p[i][j]=p[k][j];  
73:                           }  
74:                      }  
75:                 }  
76:       }  
77:       cout<<"Modified ASSP MATRIX is:->";  
78:       for(int i=1;i<n+1;i++)  
79:    {  
80:            std::cout<<endl;  
81:            for(int j=1;j<n+1;j++)  
82:            {  
83:                printf("%5d",d[i][j]);  
84:            }  
85:    }  
86:    cout<<endl<<"Parent MATRIX is:->";  
87:    for(int i=1;i<n+1;i++)  
88:    {  
89:            std::cout<<endl;  
90:            for(int j=1;j<n+1;j++)  
91:            {  
92:                printf("%5d",p[i][j]);  
93:            }  
94:    }  
95:    cout<<endl<<endl;  
96:    for(int i=1;i<n+1;i++)  
97:    {  
98:            for(int j=1;j<n+1;j++)  
99:            {  
100:                 if(i!=j)  
101:                 {  
102:                      cout<<"Shortes Path from node "  
103:                        <<i <<" to node "<<j  
104:                        <<" :- cost= "<<d[i][j];  
105:                      cout<<"::path is "<<i;  
106:                      path(i,j,p);  
107:                 }  
108:                 cout<<endl;  
109:            }  
110:       }  
111:       /*cout<<endl;  
112:       cout<<"1";  
113:    path(1,2,p);*/  
114:       return 0;  
115:  }  

For Further info goto :- http://securityresearch.in/beta/