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/
