#include<iostream.h>
#include<conio.h>
class tsal
{
private:
int a[10][10],visited[10],n,cost;
public:
tsal()
{
cost=0;
}
void get()
{
int i,j;
cout<<"Enter no. of cities: ";
cin>>n;
cout<<"\nEnter cost matrix:\n";
for(i=0;i<n;i++)
{
cout<<"Enter elements of the row: "<<i+1<<"\n";
for(j=0;j<n;j++)
cin>>a[i][j];
visited[i]=0;
}
clrscr();
cout<<"\n\nThe cost list is:\n\n";
for(i=0;i<n;i++)
{
cout<<"\n\n";
for(j=0;j<n;j++)
cout<<" "<<a[i][j];
}
}
void mincost(int city)
{
int i,ncity;
visited[city]=1;
cout<<city+1<<"-->";
ncity=least(city);
if(ncity==999)
{
ncity=0;
cout<<ncity+1;
cost+=a[city][ncity];
return;
}
mincost(ncity);
}
int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i<n;i++)
{
if((a[c][i]!=0)&&(visited[i]==0))
if(a[c][i]<min)
{
min=a[i][0]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}
voidput()
{
cout<<"\n\nMinimum cost: ";
cout<<cost;
}
};
voidmain()
{
tsal t;
clrscr();
t.get();
cout<<"\n\nPath is: \n\n";
t.mincost(0);
t.put();
getch();
}
Comments
Post a Comment