Program to solve travelling sales person problem using dynamic programming

// program to solve travelling sales person problem using dynamic programming

#include <iostream.h>
#include<conio.h>

#define MAX 100
#define INFINITY 999

class travel
{
	private:
		int n; /* Number of cities. */
		int i, j; /* Loop counters. */
		int c[MAX][MAX]; /* Cost matrix. */
		int tour[MAX]; /* Tour matrix. */
		int cost; /* Least cost. */
		int tsp_dp (int c[][MAX], int tour[], int start, int n);

	public:
		int tsp();
		void setdata();
		void getdata();
};

int travel::tsp()
{
	return(tsp_dp(c,tour,0,n));
}

void travel::setdata()
{
	cout<<"\nHow many cities to traverse? ";
	cin>>n;

	cout<<"\nEnter the cost matrix: (999: no connection)\n";
	for(i=0;i<n;i++)
	{
		cout<<"\nEnter "<<i+1<<" row: ";
		for(j=0;j<n;j++)
			cin>>c[i][j];
	}

	for(i=0;i<n;i++)
		tour[i]=i;

}

void travel::getdata()
{
	for (i=0; i<n; i++)
		cout<<tour[i]+1<<"\t";
	cout<<"1\n";
}

int travel::tsp_dp (int c[][MAX], int tour[], int start, int n)
{
	int i, j, k; /* Loop counters. */
	int temp[MAX]; /* Temporary during calculations. */
	int mintour[MAX]; /* Minimal tour array. */
	int mincost; /* Minimal cost. */
	int ccost; /* Current cost. */

	/* End of recursion condition. */
	if(start==n-2)
		return c[tour[n-2]][tour[n-1]] + c[tour[n-1]][0];

/* Compute the tour starting from the current city. */
	mincost = INFINITY;
	for(i=start+1;i<n;i++)
	{
		for(j=0;j<n;j++)
			temp[j]=tour[j];

/* Adjust positions. */
		temp[start+1]=tour[i];
		temp[i]=tour[start+1];

/* Found a better cycle? (Recurrence derivable.) */
		if (c[tour[start]][tour[i]] +
				(ccost = tsp_dp (c, temp, start+1, n)) < mincost)
		{
			mincost=c[tour[start]][tour[i]]+ccost;
			for(k=0;k<n;k++)
				mintour[k]=temp[k];
		}
	}

	/* Set the minimum-tour array. */
	for(i=0;i<n;i++)
		tour[i]=mintour[i];

	return mincost;
}

void main()
{
	int cost;
	travel t;
	clrscr();

	t.setdata();

	cost = t.tsp();
	cout<<"\n\n\tMinimum cost: "<<cost;
	cout<<"\n\n\tTour: \t";

	t.getdata();

	getch();
}