traveling salesman problem program in java

import java.util.*;
import java.text.*;
class TSP
{
int weight[][],n,tour[],finalCost;
//n-no. of nodes
final int INF=800;
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 setToNextCall[]=new int[n-1];
for(int i=0;i<setSize;i++)
{
int k=0;
for(int j=0;j<setSize;j++)
{
if(inputSet[i]!=inputSet[j])
setToNextCall[k++]=inputSet[j];
}
int temp=COST(inputSet[i],setToNextCall,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 setToNextCall[]=new int[n-1];
for(int i=0;i<setSize;i++)
{
int k=0;
for(int j=0;j<setSize;j++)
{
if(inputSet[i]!=inputSet[j])
setToNextCall[k++]=inputSet[j];
}
int temp=COST(inputSet[i],setToNextCall,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 travel
{
public static void main(String args[])
{
TSP obj=new TSP();
}
}
/*

traveling salesman problem program output:
Enter no. of nodes:
4
Enter weight of 1 to 2:20
Enter weight of 1 to 3:42
Enter weight of 1 to 4:35
Enter weight of 2 to 1:20
Enter weight of 2 to 3:30
Enter weight of 2 to 4:34
Enter weight of 3 to 1:42
Enter weight of 3 to 2:30
Enter weight of 3 to 4:12
Enter weight of 4 to 1:35
Enter weight of 4 to 2:34
Enter weight of 4 to 3:12
Starting node assumed to be node 1.
The tour is 1-2-3-4-1
The final cost is 97
*/

Facing difficulties in understanding the program ?

Ask Your Queries in Comment Box

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *