//TRAVELLING SALESMAN PROBLEM
import java.util.*;
import java.text.*;
class TSP
{
int weight[][],n,tour[],finalCost;
final int INF=1000;
public TSP()
{
Scanner s=new Scanner(System.in);
System.out.println("Enter no. of nodes:=>");
n=s.nextInt();
weight=new int[n][n];
tour=new int[n-1];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j)
{
System.out.print("Enter weight of "+(i+1)+" to "+(j+1)+":=>");
weight[i][j]=s.nextInt();
}
}
}
System.out.println();
System.out.println("Starting node assumed to be node 1.");
eval();
}
public int COST(int currentNode,int inputSet[],int setSize)
{
if(setSize==0)
return weight[currentNode][0];
int min=INF,minindex=0;
int setToBePassedOnToNextCallOfCOST[]=new int[n-1];
for(int i=0;i<setSize;i++)
{
int k=0;//initialise new set
for(int j=0;j<setSize;j++)
{
if(inputSet[i]!=inputSet[j])
setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];
}
int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);
if((weight[currentNode][inputSet[i]]+temp) < min)
{
min=weight[currentNode][inputSet[i]]+temp;
minindex=inputSet[i];
}
}
return min;
}
public int MIN(int currentNode,int inputSet[],int setSize)
{
if(setSize==0)
return weight[currentNode][0];
int min=INF,minindex=0;
int setToBePassedOnToNextCallOfCOST[]=new int[n-1];
for(int i=0;i<setSize;i++)//considers each node of inputSet
{
int k=0;
for(int j=0;j<setSize;j++)
{
if(inputSet[i]!=inputSet[j])
setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];
}
int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);
if((weight[currentNode][inputSet[i]]+temp) < min)
{
min=weight[currentNode][inputSet[i]]+temp;
minindex=inputSet[i];
}
}
return minindex;
}
public void eval()
{
int dummySet[]=new int[n-1];
for(int i=1;i<n;i++)
dummySet[i-1]=i;
finalCost=COST(0,dummySet,n-1);
constructTour();
}
public void constructTour()
{
int previousSet[]=new int[n-1];
int nextSet[]=new int[n-2]; for(int i=1;i<n;i++)
previousSet[i-1]=i;
int setSize=n-1;
tour[0]=MIN(0,previousSet,setSize);
for(int i=1;i<n-1;i++)
{
int k=0;
for(int j=0;j<setSize;j++)
{
if(tour[i-1]!=previousSet[j])
nextSet[k++]=previousSet[j];
}
--setSize;
tour[i]=MIN(tour[i-1],nextSet,setSize);
for(int j=0;j<setSize;j++)
previousSet[j]=nextSet[j];
}
display();
}
public void display()
{
System.out.println();
System.out.print("The tour is 1-");
for(int i=0;i<n-1;i++)
System.out.print((tour[i]+1)+"-");
System.out.print("1");
System.out.println();
System.out.println("The final cost is "+finalCost);
}
}
class TSPExp
{
public static void main(String args[])
{
TSP obj=new TSP();
}
}
SAMPLE OUTPUT :
Enter no. of nodes:=>
5
Enter weight of 1 to 2:=>4
Enter weight of 1 to 3:=>6
Enter weight of 1 to 4:=>3
Enter weight of 1 to 5:=>7
Enter weight of 2 to 1:=>3
Enter weight of 2 to 3:=>1
Enter weight of 2 to 4:=>7
Enter weight of 2 to 5:=>4
Enter weight of 3 to 1:=>7
Enter weight of 3 to 2:=>4
Enter weight of 3 to 4:=>3
Enter weight of 3 to 5:=>6
Enter weight of 4 to 1:=>8
Enter weight of 4 to 2:=>5
Enter weight of 4 to 3:=>3
Enter weight of 4 to 5:=>2
Enter weight of 5 to 1:=>4
Enter weight of 5 to 2:=>3
Enter weight of 5 to 3:=>2
Enter weight of 5 to 4:=>1
Starting node assumed to be node 1.
The tour is 1-2-3-4-5-1
The final cost is 14
Press any key to continue...