Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
- package butlergraph;
- import java.util.ArrayList;
- /**
- *
- * @author Bernard Bailey
- */
- public class FindShortestPath extends ButlerGraph {
- double shortestDistance=Double.MAX_VALUE;
- double currentDistance=0.0;
- ButlerGraph recGraph = new ButlerGraph();
- String[] shortestPath = new String [8];
- ArrayList<Integer> bestPath = new ArrayList<>();
- ButlerGraph f = new ButlerGraph();
- double distanceRec = f.getDistance(1, 0);
- int nodeSize = f.getSize();
- int node;
- int next_node;
- boolean [] noVd = new boolean[7];
- public void findShortestDistance(int node,double cityDistance,ArrayList currentPath){
- // Add this node to the list of nodes visited so far
- currentPath.add(node);
- // If all nodes have been visited (the base case)
- if (currentPath.size() == nodeSize-1)// base case
- {
- // Complete the circuit by adding the distance back to the start
- cityDistance += f.getDistance(node, 1);
- currentPath.add(1);
- // If the distance is better than the best distance found so far,
- if (cityDistance<shortestDistance){
- shortestDistance=cityDistance;
- bestPath=currentPath;
- noVd[node] = true;
- }
- else{
- noVd[node] = false;
- }
- // Before backtracking, remove this node from the list of nodes visited
- // TODO
- if (noVd[node] == true){
- shortestDistance = shortestDistance - f.getDistance(node, node-1);
- currentPath.remove(currentPath.size()-1);
- }
- for(node=0;node<currentPath.size()-1;node++){
- if (currentPath.indexOf(0)==1){
- int next_node = node +1;
- }
- else {next_node = node +1;}
- if ((noVd[node]==false) && (currentPath.indexOf(node)>0) ){
- noVd[node]=true;
- double nextDistance = cityDistance+f.getDistance(node,next_node);
- findShortestDistance(next_node,nextDistance,currentPath);
- }
- }
- // Backtrack by returning so that you can try other paths
- return;
- }
- else{int next_node=0;
- for (node=0;node<currentPath.size()-1;node++){
- // For loop over indices 0 through 6
- // If current index is in currentPath, skip it
- if ((noVd[node])==false&&(node<=currentPath.size()-1)){
- next_node=node;
- }
- else{
- next_node=1;
- }
- // Otherwise recurse
- }// get distance to new node --
- double nextDistance = cityDistance+f.getDistance(node,next_node);
- findShortestDistance(next_node,nextDistance,currentPath);
- return;
- }
- }
- public static void main(String[] args) {
- FindShortestPath cPath = new FindShortestPath();
- // find the shortest path recursively
- ArrayList<Integer> currentPath = new ArrayList<Integer>();
- cPath.findShortestDistance(1, 0, currentPath);
- // Extract shortest path from class
- System.out.println(cPath.shortestDistance);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement