Advertisement
BABJ

Updated findShortestPath

Nov 9th, 2019
543
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.56 KB | None | 0 0
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package butlergraph;
  7.  
  8. import java.util.ArrayList;
  9.  
  10. /**
  11.  *
  12.  * @author Bernard Bailey
  13.  */
  14. public class FindShortestPath extends ButlerGraph {
  15.     double shortestDistance=Double.MAX_VALUE;
  16.     double currentDistance=0.0;
  17.     ButlerGraph recGraph = new ButlerGraph();
  18.     String[] shortestPath = new String [8];
  19.     ArrayList<Integer> bestPath = new ArrayList<>();
  20.     ButlerGraph f = new ButlerGraph();
  21.     double distanceRec = f.getDistance(1, 0);
  22.     int nodeSize = f.getSize();
  23.     int node;
  24.     int next_node;
  25.     boolean [] noVd = new boolean[7];
  26.     public void findShortestDistance(int node,double cityDistance,ArrayList currentPath){
  27.        // Add this node to the list of nodes visited so far
  28.        currentPath.add(node);
  29.        
  30.        
  31.        // If all nodes have been visited (the base case)
  32.         if (currentPath.size() == nodeSize-1)// base case
  33.         {
  34.             // Complete the circuit by adding the distance back to the start
  35.             cityDistance += f.getDistance(node, 1);
  36.             currentPath.add(1);
  37.             // If the distance is better than the best distance found so far,
  38.             if (cityDistance<shortestDistance){
  39.             shortestDistance=cityDistance;
  40.             bestPath=currentPath;    
  41.            
  42.             noVd[node] = true;
  43.             }
  44.             else{
  45.             noVd[node] = false;
  46.             }
  47.             // Before backtracking, remove this node from the list of nodes visited
  48.             // TODO
  49.            
  50.             if (noVd[node] == true){
  51.              shortestDistance = shortestDistance - f.getDistance(node, node-1);
  52.              currentPath.remove(currentPath.size()-1);
  53.             }
  54.             for(node=0;node<currentPath.size()-1;node++){
  55.                 if (currentPath.indexOf(0)==1){
  56.                  int next_node = node +1;
  57.                 }
  58.                 else {next_node = node +1;}
  59.                 if ((noVd[node]==false) && (currentPath.indexOf(node)>0) ){
  60.                     noVd[node]=true;
  61.                     double nextDistance = cityDistance+f.getDistance(node,next_node);
  62.                     findShortestDistance(next_node,nextDistance,currentPath);
  63.                
  64.                 }
  65.             }
  66.             // Backtrack by returning so that you can try other paths
  67.             return;
  68.         }
  69.         else{int next_node=0;
  70.             for (node=0;node<currentPath.size()-1;node++){
  71.             // For loop over indices 0 through 6
  72.                 // If current index is in currentPath, skip it
  73.                 if ((noVd[node])==false&&(node<=currentPath.size()-1)){
  74.                 next_node=node;
  75.                 }
  76.                 else{
  77.                 next_node=1;
  78.                 }
  79.                 // Otherwise recurse
  80.             }// get distance to new node --
  81.                 double nextDistance = cityDistance+f.getDistance(node,next_node);
  82.                 findShortestDistance(next_node,nextDistance,currentPath);
  83.                 return;
  84.         }
  85.        
  86.        
  87. }
  88.     public static void main(String[] args) {
  89.         FindShortestPath cPath = new FindShortestPath();
  90.         // find the shortest path recursively
  91.         ArrayList<Integer> currentPath = new ArrayList<Integer>();
  92.         cPath.findShortestDistance(1, 0, currentPath);
  93.         // Extract shortest path from class
  94.         System.out.println(cPath.shortestDistance);
  95.     }
  96.    
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement