Find the final path of Traveling Salesman Problem-CodePudding

I am trying to implement the Traveling Salesman Problem and I need to return the path that lead to the minimum cost. I have a distance matrix, and this is the code:

static int TSP(int[][] distance, boolean[] visitCity, int currPos, int cities, int count, int cost, int result)
{
    if (count == cities && distance[currPos][0] > 0) {

        result = Math.min(result, cost   distance[currPos][0]);

        return result;
    }
    
    for (int i = 0; i < cities; i  )
    {
        if (visitCity[i] == false && distance[currPos][i] > 0)
        {
            visitCity[i] = true;

            result = TSP(distance, visitCity, i, cities, count   1, cost   distance[currPos][i], result);

            visitCity[i] = false;
        }
    }
    return result;
}

I call this method like this:

boolean[] visitCity = new boolean[cities];
visitCity[0] = true;
int result = Integer.MAX_VALUE;
result = TSP(distance, visitCity, 0, cities, 1, 0, result);

In the end, the algorithm print the cost of the path, but I also need it to print the path that lead to this. Like "0->1->3->2->etc->0". Is there any posibility to achieve that?

CodePudding user response：

So, before giving a possible solution to your question i want to say, if you don't already know, that the Travelling Salesman Problem is known as an NP-hard problem (here's the first result for the search but there's many research papers about this question:

Output:

0   4,24    1,41    4,47    1,41    2,83    
4,24    0   5,66    5,1 2,83    1,41    
1,41    5,66    0   5,1 2,83    4,24    
4,47    5,1 5,1 0   4,24    4,47    
1,41    2,83    2,83    4,24    0   1,41    
2,83    1,41    4,24    4,47    1,41    0   
Best path: (15.854893 costs): 0 -> 2 -> 3 -> 1 -> 5 -> 4 -> 0
Best path: (15.854892 costs): 1 -> 3 -> 2 -> 0 -> 4 -> 5 -> 1
Best path: (15.854892 costs): 2 -> 3 -> 1 -> 5 -> 4 -> 0 -> 2
Best path: (15.854893 costs): 3 -> 1 -> 5 -> 4 -> 0 -> 2 -> 3
Best path: (15.854893 costs): 4 -> 0 -> 2 -> 3 -> 1 -> 5 -> 4
Best path: (15.854893 costs): 5 -> 1 -> 3 -> 2 -> 0 -> 4 -> 5