Still can't find a way to return to the origin city in the TSP problem

Question

Problem Description : The travelling salesman problem (also called the travelling salesperson problem or 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 and returns to the origin city?"

My solution :

I used The Backtracking Method, and i used that Google Guava library to construct graphs the only problem is i my code don't return the initial city , by example if we have A , B , C , D cities and the shortest trajectory is A ,B , D, C we have to return to the initial city Like A ,B , D, C, A Here is the the code (or you can check the following github link to understand the problem better https://charlesreid1.github.io/solving-the-traveling-salesperson-problem-with-java-and-guava.html :

    
    package com.Faissal;
    
    import com.google.common.graph.ImmutableNetwork;
    import com.google.common.graph.MutableNetwork;
    import com.google.common.graph.NetworkBuilder;
    
    import java.util.Arrays;
    import java.util.Map;
    import java.util.Set;
    import java.util.TreeMap;
    
    
    class TSP {
        // The actual graph of cities
        ImmutableNetwork<Node, Edge> graph;
        int graphSize;
    
        // Storage variables used when searching for a solution
        String[] route;        // store the route
        double this_distance;   // store the total distance
        double min_distance;    // store the shortest path found so far
    
        /**
         * Defaut constructor generates the graph and initializes storage variables
         */
        public TSP() {
            // Build the graph
            this.graph = buildGraph();
            this.graphSize = this.graph.nodes().size();
    
            // Initialize route variable, shared across recursive method instances
            this.route = new String[this.graphSize];
    
            // Initialize distance variable, shared across recursive method instances
            this.this_distance = 0.0;
            this.min_distance = -1.0; // negative min means uninitialized
        }
    
        /**
         * This method actually constructs the graph.
         */
        public ImmutableNetwork<Node, Edge> buildGraph() {
    
            // MutableNetwork is an interface requiring a type for nodes and a type for edges
            MutableNetwork<Node, Edge> roads = NetworkBuilder.undirected().build();
    
            // Construct Nodes for cities,
            // and add them to a map
            String[] cities = {"Wuhan", "shanghai", "Beijing", "Tianjin", "dalian"};
            Map<String, Node> all_nodes = new TreeMap<String, Node>();
            for (int i = 0; i < cities.length; i++) {
                // Add nodes to map
                Node node = new Node(cities[i]);
                all_nodes.put(cities[i], node);
    
                // Add nodes to network
                roads.addNode(node);
            }
    
            // Construct Edges for roads,
            // and add them to a map
            String[] distances = {"Wuhan:shanghai:839", "Wuhan:Beijing:1153", "Wuhan:Tianjin:1162", "Wuhan:dalian:1423", "shanghai:Beijing:1214", "shanghai:Tianjin:20", "Beijing:Tianjin:4", "shanghai:dalian:1076", "Tianjin:dalian:802"};
            Map<String, Edge> all_edges = new TreeMap<String, Edge>();
            for (int j = 0; j < distances.length; j++) {
                // Parse out (city1):(city2):(distance)
                String[] splitresult = distances[j].split(":");
                String left = splitresult[0];
                String right = splitresult[1];
                String label = left + ":" + right;
                int value = Integer.parseInt(splitresult[2]);
    
                // Add edges to map
                Edge edge = new Edge(left, right, value);
                all_edges.put(label, edge);
    
                // Add edges to network
                roads.addEdge(all_nodes.get(edge.left), all_nodes.get(edge.right), edge);
            }
    
            // Freeze the network
            ImmutableNetwork<Node, Edge> frozen_roads = ImmutableNetwork.copyOf(roads);
    
            return frozen_roads;
        }
    
        /**
         /** Public solve method will call the recursive backtracking method to search for solutions on the graph */
        public void solve() {
            /** To solve the traveling salesman problem:
             * Set up the graph, choose a starting node, then call the recursive backtracking method and pass it the starting node.
             */
    
            // We need to pass a starting node to recursive backtracking method
            Node startNode = null;
    
            // Grab a node, any node...
            for( Node n : graph.nodes() ) {
                startNode = n;
                break;
            }
    
            // Visit the first node
            startNode.visit();
    
            // Add first node to the route
            this.route[0] = startNode.label;
    
            // Pass the number of choices made
            int nchoices = 1;
    
            // Recursive backtracking
            explore(startNode, nchoices);
        }
    
        /** Recursive backtracking method: explore possible solutions starting at this node, having made nchoices */
        /**
         * Recursive backtracking method: explore possible solutions starting at this node, having made nchoices
         * @return
         */
        public void explore(Node node, int nchoices) {
            /**
             * Solution strategy: recursive backtracking.
          */
    
            if (nchoices == graphSize) {
                //
                // BASE CASE
                //
                if (this.this_distance < this.min_distance || this.min_distance < 0) {
                    // if this_distance < min_distance, this is our new minimum distance
                    // if min_distance < 0, this is our first minimium distance
                    this.min_distance = this.this_distance;
    
                    printSolution();
    
    
                } else {
                    printFailure();
                }
    
            } else {
                //
                // RECURSIVE CASE
                //
                Set<Node> neighbors = graph.adjacentNodes(node);
                for (Node neighbor : neighbors) {
                    if (neighbor.visited == false) {
    
                        int distance_btwn = 0;
    
                        for (Edge edge : graph.edgesConnecting(node, neighbor)) {
                            distance_btwn = edge.value;
                        }
    
                        // Make a choice
                        this.route[nchoices] = neighbor.label;
                        neighbor.visit();
                        this.this_distance += distance_btwn;
    
                        // Explore the consequences
                        explore(neighbor, nchoices + 1);
    
                        // Unmake the choice
                        this.route[nchoices] = null;
                        neighbor.unvisit();
                        this.this_distance -= distance_btwn;
                    }
    
                    // Move on to the next choice (continue loop)
                }
    
            } // End base/recursive case
    
    
        }
    
    
        public void printSolution() {
    
            System.out.print("***********\tNEW SOLUTION\t");
            System.out.println("Route: " + Arrays.toString(this.route)
                    + "\tDistance: " + this.min_distance);
        }
    
        /**
         * Do nothing with failed path
         */
        public void printFailure() {
            //
        }
    }

The Node Class is 
``` 

class Node {
    public String label;
    public boolean visited; // Helps us to keep track of where we've been on the graph
    public Node(String name){
        this.label = name;
        this.visited = false;
    }
    public void visit(){
        this.visited = true;
    }
    public void unvisit() {
        this.visited = false;
    }
}

  The Edge Class :
  ``` 
  class Edge {
      public int value;
      public String left, right; // For convenience in construction process. Not necessary.
      public Edge(String left, String right, int value) {
          this.left = left;
          this.right = right;
          this.value = value;
      }
  }

  

The main class

``` 


public class Main {

    public static void main(String[] args) {
        
        TSP t = new TSP();
        t.solve();
    }
}

I will be very Thankful if someone helped me with this issue

Answer 1

You're almost there, you just have to move back to the origin.

For that you have to have a reference of the origin in TSP.explore. You could store it somewhere in this.startNode or make route an array of Nodes: Node[] route

Then you can check in TSP.explore, if the last node has the origin as its neighbor, add that distance to the total distance and go on like usual.

It basically comes down to this:

// Store Nodes instead of Strings. Edit this everywhere you use it.
Node[] route; 

// ...

if (nchoices == graphSize) {
    //
    // BASE CASE: VISITED EACH NODE
    //
    Set<Node> neighbors = graph.adjacentNodes(node);

    // It's only a solution, if there is a edge to the first node.
    if(neighbors.contains(this.route[0])) {

        // Same computation as in the else-block.
        int distance_btwn = this.getDistanceBetween(node, neighbor);
    
        // Add the distance to the start node.
        int total_distance = this.this_distance + distance_btwn;

        if (total_distance < this.min_distance || this.min_distance < 0) {
            // if this_distance < min_distance, this is our new minimum distance
            // if min_distance < 0, this is our first minimium distance
            this.min_distance = total_distance;

            // You have to tell printSolution to about total_distance somehow.
            printSolution(total_distance);
            return;
        } 
    }
        
    printFailure();
}