This is a java program to solve TSP. The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
Here is the source code of the Java Program to Solve Travelling Salesman Problem for Unweighted Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.graph; import java.util.InputMismatchException; import java.util.Scanner; public class TSP { private int numberOfNodes; private Stack<Integer> stack; public TSP() { 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 + "\t"); 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 + "\t"); 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 cities are visited as follows: "); TSP tspNearestNeighbour = new TSP(); tspNearestNeighbour.tsp(adjacency_matrix); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } scanner.close(); } }
Output:
$ javac TSP.java $ java TSP Enter the number of nodes in the graph 9 Enter the adjacency matrix 000 374 200 223 108 178 252 285 240 356 374 000 255 166 433 199 135 095 136 017 200 255 000 128 277 128 180 160 131 247 223 166 128 000 430 047 052 084 040 155 108 433 277 430 000 453 478 344 389 423 178 199 128 047 453 000 091 110 064 181 252 135 180 052 478 091 000 114 083 117 285 095 160 084 344 110 114 000 047 078 240 136 131 040 389 064 083 047 000 118 356 017 247 155 423 181 117 078 118 000 The cities are visited as follows: 1 5 3 2 9 7 4 6 8
Related posts:
Java Program to Implement Park-Miller Random Number Generation Algorithm
Guide to java.util.concurrent.Locks
Converting Between a List and a Set in Java
Kết hợp Java Reflection và Java Annotations
Introduction to Spring Method Security
Java – String to Reader
Guide to Java OutputStream
Spring Autowiring of Generic Types
A Guide to Apache Commons Collections CollectionUtils
Từ khóa this và super trong Java
Java Program to Perform Cryptography Using Transposition Technique
Guide to the Java TransferQueue
Tính kế thừa (Inheritance) trong java
Java Program to Implement Floyd Cycle Algorithm
Guide to Dynamic Tests in Junit 5
Hướng dẫn Java Design Pattern – Command
Write/Read cookies using HTTP and Read a file from the internet
Tạo ứng dụng Java RESTful Client với thư viện Retrofit
Java Program to Implement Hopcroft Algorithm
Java Program to Create a Random Linear Extension for a DAG
Java Program to Implement DelayQueue API
Spring Boot - Bootstrapping
Error Handling for REST with Spring
Java Program to Check Multiplicability of Two Matrices
Comparing Long Values in Java
The DAO with JPA and Spring
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
How to Find an Element in a List with Java
Sorting Query Results with Spring Data
Java Program to Implement Counting Sort
Java Program to Implement the String Search Algorithm for Short Text Sizes
Hướng dẫn Java Design Pattern – Transfer Object