Salesman Problem in Java

The Traveling Salesman Problem determines the shortest path that visits each city approximately once and loops back to the starting location. Another Java problem that is most like the Traveling Salesman's Problem is the Hamiltonian Cycle.

The fundamental contrast between TSP and the Hamiltonian cycle is that within the other, we must determine whether such a tour that stops in each city precisely once already exists. A Hamiltonian cycle is always present in the Traveling Salesman Problem since the graph is complete. The goal is to identify a Hamiltonian cycle with the least weight.

Solution

The most well-known computing problem is the traveling salesman problem. We can apply a brute-force strategy to compare every trip and choose the best one. A graph has (n - 1) vertices for every n vertices. A multitude of potential outcomes.

Although no polynomial time algorithm exists, dynamic programming can achieve the solution in less time.

Consider the graph G = (V, E), which consists of a collection of cities as nodes and a set of weighted edges as edges. The connection between vertices u and v is shown by the edge e(u, v). Vertex u and v are separated by a distance called d(u, v), which must not be negative.

Consider that after visiting a few cities, we are now in city j, having started at city 1. So, this is only a portion of the tour. Since j will determine which towns are the most convenient to visit next, we must unquestionably know it. To avoid repetition, we must also be aware of every city we have visited. As a result, this is the right sub-problem.

Let C(S, j) be the lengths of the Shortest Distance traversing each node in S exactly once, beginning at 1, and ending at j, for a subgroup of cities S 1, 2, 3,..., n that contains 1, and j in S.

Considering that the path cannot continue and terminate at 1, we define C(S, 1) = when |S| > 1.

Let's break C(S, j) into more manageable subproblems. Starting at 1 and ending at j is what we need to do. The city should choose in the following way.

C(S,j)=minC(S-{j},i)+d(i,j) where i∈Sandi≠j

c(S,j)=minC(s-{j},i)+d(i,j) where I∈Sandi≠j

Algorithm

C ({1}, 1) = 0 
for s = 2 to N, do 
   for all the subsets of Sub Є {1, 2, 3, … , N} of size S and containing 1 
      C (Sub, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (Sub, j) = min {C (Sub– {j}, i) + d(i, j) for i Є Sub and i ≠ j} 
return minj C ({1, 2, 3, …, N}, j) + d(j, i) 

Implementing the Traveling Salesman Problem

We employ the subsequent stages to implement the TSP program in Java:

• We look at a city as the beginning and the end. Because the route is circular, we can start in any city.
• According to the DFS method, we begin by traversing from the source to its nearby nodes.
• Determine the price of each traversal, maintain a note of the lowest price, and continually update the value of the minimum price stored value.
• Return the permutation with the lowest cost in the end.

Filename: SalesmanProblem.java

// Java program for salesman problem
//importing required packages
import java.util.*;   
import java.io.*;   
import java.util.Scanner;  
// A class is created to implement code   
class SalesmanProblem
{  
    // the method findHamiltonianCycles() for finding the cycles of all cities
    static int findHamiltonianCycles(int[][] distances, boolean[] visitCities, int currPosition, int city, int counts, int costs, int hamiltonianCycles)   
    {  
    
        if (counts == city && distances[currPosition][0] > 0)   
        {  
            hamiltonianCycles = Math.min(hamiltonianCycles, costs + distances[currPosition][0]);  
            return hamiltonianCycles;  
        }  
    
        // the step for interacting over the paths
        for (int i = 0; i < city; i++)   
        {  
            if (visitCities[i] == false && distances[currPosition][i] > 0)   
            {  
                // stores if it is visited
                visitCities[i] = true;  
                hamiltonianCycles = findHamiltonianCycles(distances, visitCities, i, city, counts + 1, costs + distances[currPosition][i],                     
                  hamiltonianCycles);  
                // The node which is not visited is marked  
                visitCities[i] = false;  
            }  
        }  
        return hamiltonianCycles;  
    } 
    // main section of the program
    public static void main(String[] args)  
    {  
        int city;  
        // The Scanner class object is created for gettig the input from the user as distance
        Scanner sca = new Scanner(System.in);  
        // Entering the number of cities 
        System.out.println("Enter the total number of cities:");  
        city = sca.nextInt();  
        // reading the cities’ distances
        int distances[][] = new int[city][city];  
        for( int i = 0; i < city; i++){  
            for( int j = 0; j < city; j++){  
                System.out.println("The Distance between the cities "+ (i+1) +" to cities"+ (j+1) +": ");  
                distances[i][j] = sca.nextInt();  
            }  
        }  
        // A boolean array is created for storing the boolean values for storing the cities visited or unvisited
        boolean[] visitCities = new boolean[city];  
        // The first city is marked as visited 
        visitCities[0] = true;  
        int hamiltonianCycles = Integer.MAX_VALUE;  
        // call findHamiltonianCycles() method that returns the path, which consists of minimal path
        hamiltonianCycles = findHamiltonianCycles(distances, visitCities, 0, city, 1, 0, hamiltonianCycles);  
        // displays the cycle which contains minimum distance
        System. out.println(“The minimum distance is: ”+hamiltonianCycles);  
    }  
}  

Output

Enter the total number of cities:
5
The Distance between the cities 1 to cities1: 
23
The Distance between the cities 1 to cities2: 
18
1The Distance between the cities 1 to cities3:
5
The Distance between the cities 1 to cities4: 
35
The Distance between the cities 1 to cities5: 
12
The Distance between the cities 2 to cities1: 
45
The Distance between the cities 2 to cities2: 
124
The Distance between the cities 2 to cities3: 
34
1The Distance between the cities 2 to cities4: 
8
2The Distance between the cities 2 to cities5: 
9
The Distance between the cities 3 to cities1: 
34
The Distance between the cities 3 to cities2: 
56
The Distance between the cities 3 to cities3: 
3
The Distance between the cities 3 to cities4: 
23
The Distance between the cities 3 to cities5:
23
The Distance between the cities 4 to cities1: 
6
The Distance between the cities 4 to cities2: 
34
The Distance between the cities 4 to cities3: 
89
The Distance between the cities 4 to cities4: 
35
The Distance between the cities 4 to cities5: 
64
The Distance between the cities 5 to cities1: 
91
The Distance between the cities 5 to cities2: 
25
The Distance between the cities 5 to cities3: 
39
The Distance between the cities 5 to cities4: 
54
The Distance between the cities 5 to cities5: 
49
The minimum distance is:67

Time complexity: O(N!)

The node will contain the n possibilities; the second will contain n-1 possibilities, and so on.

Space Complexity: O(N)