This is code for the Traveling Saleperson problem. I need to implement code that
ID: 643938 • Letter: T
Question
This is code for the Traveling Saleperson problem.
I need to implement code that will also print the total length of the shortest tour then display that total distance in the output.
Here is my current code, and the current matrix I am using.
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class TSPNearestNeighbour
{
private int numberOfNodes;
private Stack<Integer> stack;
public TSPNearestNeighbour()
{
stack = new Stack<Integer>();
}
public void tsp(int adjacencyMatrix[][])
{
numberOfNodes = adjacencyMatrix[1].length - 1;
int[] visited = new int[numberOfNodes + 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 <= numberOfNodes)
{
if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)
{
if (min > adjacencyMatrix[element][i])
{
min = adjacencyMatrix[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 the 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 adjacency 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 citys are visited as follows");
TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour();
tspNearestNeighbour.tsp(adjacency_matrix);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
Then here is the matrix:
-1 1075 716 792 1425 1369 740 802 531 383 811 2211 661 870 999 772 1075 -1 1015 1770 2403 1662 870 1858 941 1426 1437 3026 1486 211 1463 314 716 1015 -1 928 1483 646 390 1085 185 749 530 2034 1377 821 471 772 792 1770 928 -1 633 1089 1111 246 908 409 495 1447 1317 1565 672 1470 1425 2403 1483 633 -1 9999 1630 752 1432 9999 931 814 1938 2198 1016 2103 1369 1662 646 1089 9999 -1 820 1335 832 9999 605 1839 2030 1468 421 1419 740 870 390 1111 1630 820 -1 1224 360 965 690 2197 1480 750 630 705 802 1858 1085 246 752 1335 1224 -1 1021 442 737 1566 1190 1653 918 1558 531 941 185 908 1432 832 360 1021 -1 685 496 2088 1192 736 616 656 383 1426 749 409 9999 9999 965 442 685 -1 738 1858 1938 1221 926 1126 811 1437 530 495 931 605 690 737 496 738 -1 1631 1472 1232 188 1152 2211 3026 2034 1447 814 1839 2197 1566 2088 1858 1631 -1 2752 2824 1563 2744 661 1486 1377 1317 1938 2030 1480 1190 1192 1938 1472 2752 -1 1281 1660 1183 870 211 821 1565 2198 1468 750 1653 736 1221 1232 2824 1281 -1 1269 109 999 1463 471 672 1016 421 630 918 616 926 188 1563 1660 1269 -1 1220 772 314 772 1470 2103 1419 705 1558 656 1126 1152 2744 1183 109 1220 -1
Explanation / Answer
Program code:
Program code:
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class TSPNearestNeighbour
{
static int adjacency_matrix[][];
private int numberOfNodes;
private Stack<Integer> stack;
public TSPNearestNeighbour()
{
stack = new Stack<Integer>();
}
public void tsp(int adjacencyMatrix[][])
{
numberOfNodes = adjacencyMatrix[1].length - 1;
int[] visited = new int[numberOfNodes + 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 <= numberOfNodes)
{
if (adjacencyMatrix[element][i] > 1
&& visited[i] == 0)
{
if (min > adjacencyMatrix[element][i])
{
min = adjacencyMatrix[element][i];
dst = i;
minFlag = true;
}
}
i++;
}
if (minFlag)
{
visited[dst] = 1;
stack.push(dst);
System.out.print(dst + " ");
minFlag = false;
continue;
}
stack.pop();
}
}
//main function
public static void main(String args[])
{
int number_of_nodes = 0;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
adjacency_matrix = new int[number_of_nodes][number_of_nodes];
System.out.println("Enter the adjacency matrix");
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
adjacency_matrix[i][j] = scanner.nextInt();
}
System.out.println();
}
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; 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 actual data entered is: ");
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
System.out.print(adjacency_matrix[i][j]+ " ");
}
System.out.println();
}
System.out.println("The city’s are visited as follows");
TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour();
tspNearestNeighbour.tsp(adjacency_matrix);
}
catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
dijkstra(number_of_nodes, 0);
scanner.close();
}
static void dijkstra(int num, int source)
{
int dist[] = new int[num];
int INT_MAX = Integer.MAX_VALUE;// The output array. dist[i] will hold
// the shortest
// distance from src to i
boolean sptSet[] = new boolean[num]; // sptSet[i] will true if vertex i
// is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < num; i++)
{
dist[i] = INT_MAX;
sptSet[i] = false;
}
// Distance of source vertex from itself is always 0
dist[source] = 0;
// Find shortest path for all vertices
for (int count = 0; count < num - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet, num);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < num; v++)
// Update dist[v] only if is not in sptSet, there is an edge
// from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && ((dist[u] + adjacency_matrix[u][v]) < dist[v]))
{
dist[v] = dist[u]+ adjacency_matrix[u][v];
}
}
// print the constructed distance array
printSolution(dist, num);
}
// minDistance method returns the minimum distance that is note till
// now
static int minDistance(int dist[], boolean sptSet[],
int V)
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index = 0;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
// printSolution will display the distance that is traveled
// and the total distance that is traveled
static void printSolution(int dist[], int n)
{
int totalDistance = 0;
System.out.println("Vertex Distance from Source ");
for (int i = 0; i < n; i++)
{
System.out.printf("%d %d ", (i+1), dist[i]);
totalDistance += dist[i];
}
System.out
.println("Therefore the total distance travelled is: "
+ totalDistance);
}
}
Sample output:
Enter the number of nodes in the graph
5
Enter the adjacency matrix
3
2
3
2
4
6
1
8
7
2
5
4
6
1
98
8
4
5
3
4
7
2
5
4
6
The actual data entered is:
3 2 3 2 4
6 1 8 7 2
5 4 6 1 98
8 4 5 3 4
7 2 5 4 6
The city’s are visited as follows
1 4 3 2
Vertex Distance from Source
1 0
2 2
3 3
4 2
5 4
Therefore the total distance travelled is: 11
Note:
The code is highlighted in bold letters. Please go through.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.