# Traveling Salesman Recursion Problem

Nov 8th, 2019
92
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 [8];
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