BABJ

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
  19. currentPath.add(node);
  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);
  26. currentPath.add(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