0

This is the code that I have done so far:

```
import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
class TSP extends JPanel{
int weight[][],n,tour[],optDist;
final int INF=1000;
public TSP(){
Scanner s=new Scanner(System.in);
Random r = new Random();
System.out.println("Enter no. of Cities:=>");
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]=1+r.nextInt(100);
}
}
}
System.out.println();
System.out.println("Starting node assumed to be node 1.");
eval();
}
public int DIST(int currentNode,int inputSet[],int setSize){
if(setSize==0)
return weight[currentNode][0];
int min=INF,minindex=0;
int setToBePassedOnToNextCallOfDIST[]=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])
setToBePassedOnToNextCallOfDIST[k++]=inputSet[j];
}
int temp=DIST(inputSet[i],setToBePassedOnToNextCallOfDIST,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=DIST(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;
optDist=DIST(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 optimal distance is "+optDist);
}
}
}
```

This code is able to output the correct tour with the optimal distance.

## Output example:

Enter no. of Cities:=>

9

Starting node assumed to be node 1.

The tour is 1-5-4-2-6-9-3-8-7-1

The optimal distance is 186

Now I have to draw the Optimal tour on a graphics window using Java Swing.

I tried using this code:

```
public void paintComponent(Graphics g){
super.paintComponent(g);
this.setBackground(Color.WHITE);
g.setColor(Color.BLACK);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
Dimension size = getSize();
Insets insets = getInsets();
int w = size.width - insets.left - insets.right;
int h = size.height - insets.top - insets.bottom;
//Random r = new Random();
//int x = Math.abs(1+r.nextInt(100)) % w;
//int y = Math.abs(1+r.nextInt(100)) % h;
int x=weight[0][j];
int y=weight[i][0];
g.fillOval(x, y, 6, 6);
}
}
```

However, it is not able to show the optimal tour.

## Example of required graphical window

By the way this is the first time I am doing projects in Java Language.