• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Traveling Salesman Recursion Problem BABJ  Nov 8th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.util.ArrayList;
2.
3. /**
4.  *
5.  * @author Bernard Bailey
6.  */
7. public class FindShortestPath extends ButlerGraph {
8.     double shortestDistance=Double.MAX_VALUE;
9.     double currentDistance=0.0;
10.     ButlerGraph recGraph = new ButlerGraph();
11.     String[] shortestPath = new String ;
12.     ArrayList<Integer> bestPath = new ArrayList<>();
13.     ButlerGraph f = new ButlerGraph();
14.     double distanceRec = f.getDistance(1, 0);
15.     int nodeSize = f.getSize();
16.
17.     public void findShortestDistance(int node,double cityDistance,ArrayList currentPath){
18.        // Add this node to the list of nodes visited so far
20.         boolean nodeVisited=false;
21.        // If all nodes have been visited (the base case)
22.         if (currentPath.size() == nodeSize)// base case
23.         {
24.             // Complete the circuit by adding the distance back to the start
25.             cityDistance += f.getDistance(node, 1);
27.             // If the distance is better than the best distance found so far,
28.             if (cityDistance<shortestDistance){
29.             shortestDistance=cityDistance;
30.             bestPath=currentPath;
31.
32.             nodeVisited = true;
33.             }
34.             else{
35.             nodeVisited = false;
36.             }
37.             // Before backtracking, remove this node from the list of nodes visited
38.             // TODO
39.
40.             if (nodeVisited == true){
41.              shortestDistance = shortestDistance - f.getDistance(node, node-1);
42.              currentPath.remove(currentPath.size()-1);
43.             }
44.
45.             // Backtrack by returning so that you can try other paths
46.             return;
47.         }
48.         else{int next_node=0;
49.             for (node=0;node<currentPath.size();node++){
50.             // For loop over indices 0 through 6
51.                 // If current index is in currentPath, skip it
52.                 if (nodeVisited==false){
53.                 next_node=node;
54.                 }
55.                 // Otherwise recurse
56.             }// get distance to new node --
57.                 double nextDistance = cityDistance+f.getDistance(node,next_node);
58.                 findShortestDistance(next_node,nextDistance,currentPath);
59.                 return;
60.         }
61.
62.
63. }
64.     public static void main(String[] args) {
65.         FindShortestPath cPath = new FindShortestPath();
66.         // find the shortest path recursively
67.         ArrayList<Integer> currentPath = new ArrayList<Integer>();
68.         cPath.findShortestDistance(1, 0, currentPath);
69.         // Extract shortest path from class
70.         System.out.println(cPath.shortestDistance);
71.     }
72.
73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top