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 [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
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. OK, I Understand
 
Top