Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<time.h>
- #include<cstdlib>
- #include<vector>
- #include<fstream>
- #define infinity 10000
- #define node int
- using namespace std;
- class path
- {
- public:
- int path[1000];
- int length;
- };
- int mat[1000][1000];
- int n;
- int cost=infinity;
- vector<node> optimal;
- void recur(int n, vector<node> v);
- int main(void)
- {
- ifstream myfile2;
- myfile2.open("input6.txt");
- cout<<"Input the size of graph: "<<endl;
- myfile2>>n;
- //
- // ofstream myfile;
- // myfile.open("input.txt");
- // srand (time(NULL));
- //
- // for(int i=0;i<n;i++)
- // {
- // for(int j=0;j<=i;j++)
- // {
- // if(i==j)
- // {
- // mat[i][j]=0;
- // continue;
- // }
- //
- // int yes;
- // yes=rand()%8;
- //
- // if(yes>=3)
- // {
- // mat[i][j]=rand()%15+1;
- // mat[j][i]=mat[i][j];
- // }
- // else
- // {
- // mat[i][j]=infinity;
- // mat[j][i]=mat[i][j];
- // }
- // }
- // }
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- myfile2>>mat[i][j];
- }
- }
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- cout<<mat[i][j]<<'\t';
- }
- cout<<endl;
- }
- // path p;
- // p.length=0;
- vector<node> v;
- v.push_back(0);
- int nod;
- nod=0;
- recur(nod,v);
- cout<<"cost: "<<cost<<endl;
- for(int i=0;i<optimal.size();i++)
- {
- cout<<optimal[i]<<' ';
- }
- }
- void recur(int nod, vector<node> v)
- {
- int localcost;
- int flag=0;
- for(int i=0;i<n;i++)
- {
- localcost=0;
- //cout<<"mat nod i = "<<mat[nod][i]<<" i "<<i<<" nod "<<nod<<endl;
- //if(i!=nod && mat[nod][i]!=infinity)
- if(i!=nod)
- {//cout<<"entered"<<endl;
- for(int j=0;j<v.size();j++)
- {
- if(v[j]==i)
- {
- flag=1;
- break;
- }
- }
- if(flag==0)
- {
- //localcost+=mat[nod][i];
- v.push_back(i);
- if(v.size()==n)
- {
- localcost=0;
- cout<<"done"<<endl;
- //cout<<"cost "<<localcost<<endl;
- for(int k=0;k<v.size();k++)
- {
- cout<<v[k]<<" ";
- if(k>0)
- {
- localcost+=mat[v[k-1]][v[k]];
- }
- }
- localcost+=mat[v[0]][v[n-1]];
- cout<<"cost "<<localcost<<endl;
- if(cost>localcost)
- {
- cost=localcost;
- while(optimal.size())
- {
- optimal.pop_back();
- }
- for(int k=0;k<v.size();k++)
- {
- optimal.push_back(v[k]);
- }
- }
- return;
- }
- else
- {
- // for(int l=0;l<v.size();l++)
- // {
- // cout<<v[l]<<' ';
- // }cout<<endl;
- //cout<<"recursion "<<i<<"\n";
- recur(i,v);
- }
- v.pop_back();
- }
- flag=0;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement