I need assistance in writing the Java code for the infamous \"TSP\" (Traveling S

Question

I need assistance in writing the Java code for the infamous "TSP" (Traveling Salesman Program). This was due last week and I am about 4 programming assignments behind, so if you know the code, please help.   We have to first develop the distance matrix, also called adjacency matrix. This adjacency matrix is populated using a given data file. You will run your program to find the best tours for 12 cities. Since this program may take too long to complete, be sure to output the tour and its cost when it finds a new best tour.

Explanation / Answer

working java code compiled on ideone

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;

public class TravelingSalesPerson
{
private int nodes;
private Stack<Integer> stack;

public TravelingSalesPerson()
{
stack = new Stack<Integer>();
}

public void tsp(int matrix[][])
{
nodes = matrix[1].length - 1;
int[] visited = new int[nodes + 1];
visited[1] = 1;
stack.push(1);
int element, dst = 0, i;
int min = Integer.MAX_VALUE;
boolean minFlag = false;
System.out.print(1 + " ");

while (!stack.isEmpty())
{
element = stack.peek();
i = 1;
min = Integer.MAX_VALUE;
while (i <= nodes)
{
if (matrix[element][i] > 1 && visited[i] == 0)
{
if (min > matrix[element][i])
{
min = matrix[element][i];
dst = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visited[dst] = 1;
stack.push(dst);
System.out.print(dst + " ");
minFlag = false;
continue;
}
stack.pop();
}
}

public static void main(String... arg)
{
int number_of_nodes;
Scanner scanner = null;
try
{
System.out.println("Enter number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the matrix");
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
adjacency_matrix[i][j] = scanner.nextInt();
}
}
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("the cities needs to be visited in this order");
TravelingSalesPerson object1 = new TravelingSalesPerson();
object1.tsp(adjacency_matrix);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Illegal Input given");
}
scanner.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.