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

Click Here

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

Do you understand what that code does? Have you been able to use it to draw some ovals or anything else? Do you have any data that defines the position/location of each Node?

Edited 3 Years Ago by JamesCherrill

I was able to get some ovals but they are all scrunched up all in one corner of the window.

Actually the weight[][] is suppose to hold the co-ordinates/ position of the cities.

I changed the paintComponent method so now the cities are aligning in one diagonal line.

Any suggestions?

That's a good start! At least we don't have to striggle with basic Swing concepts!
It looked to me like the weight array holds the distance/cost bewteen each pair of cities, yes? (It's size is n^2). I was looking for some data that holds an x and a y coordinate for each city (size 2*n). You need that to know where to draw each city because your paint routine needs to look something like this (pseudocode):

for each city
   draw a small box (or circle etc) at the x,y coordinates of the city
for each step in the tour
   draw a line from (x,y coords of the city at the start of this step) to (x,y coords of the city at the destination of this step)

Thank you sir. The program is able to show the cities now.

And I tried implementing the drawLine method but the lines are joining to only one city from other cities which does not show the appropriate tour taken.

I am not sure how should I use the tour[] to draw a line.

Any suggestions?

I assume your tour[] array just contains the city numbers in the right order, yes?

so the first line to draw is from (the x,y coords of the city identified in tour[0]) to (the x,y coords of the city identified in tour[1]). The second line is from (... tour[1]) to (... tour[2]) etc ... I'm sure you can see the pattern there and how to code that loop?

ps please don't call me "sir"
!

Edited 3 Years Ago by JamesCherrill

Thank You again JamesCherrill. The program is now able to connect the cities with the path.

I used the drawPolyLines method. However, it does not return to city number 1.

What I had done was:
After drawPolyLines i wrote drawLine from n-1(last city) to n(city 1) in the tour[]. This way also worked but i think it drew many lines from n-1 to n.

drawPolygon works perfectly.

This question has already been answered. Start a new discussion instead.