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:
Creating a Custom Starter with Spring Boot
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Check whether Directed Graph is Connected using BFS
Chuyển đổi giữa các kiểu dữ liệu trong Java
A Guide to BitSet in Java
Guide to Java 8 groupingBy Collector
Spring Webflux with Kotlin
Constructor Dependency Injection in Spring
Spring Cloud Bus
Java Program to find the number of occurrences of a given number using Binary Search approach
Spring Data JPA Delete and Relationships
Setting Up Swagger 2 with a Spring REST API
Java Program to Implement Sorted Doubly Linked List
A Guide to Spring Boot Admin
Java Program to Perform Arithmetic Operations on Numbers of Size
Java Program to Implement Sparse Matrix
Java Program to Implement CountMinSketch
Control Structures in Java
Java Program to Implement Affine Cipher
Java Program to Implement Min Heap
Intro to Spring Boot Starters
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Guide to Mustache with Spring Boot
Java Program to Perform Sorting Using B-Tree
Guide to System.gc()
Java Program to Use the Bellman-Ford Algorithm to Find the Shortest Path
Java Program to Implement Hash Tree
Java – Convert File to InputStream
Java – File to Reader
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Java Program to Implement the Vigenere Cypher
Introduction to PCollections