Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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();
- public void findShortestDistance(int node,double cityDistance,ArrayList currentPath){
- // Add this node to the list of nodes visited so far
- currentPath.add(node);
- boolean nodeVisited=false;
- // If all nodes have been visited (the base case)
- if (currentPath.size() == nodeSize)// 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;
- nodeVisited = true;
- }
- else{
- nodeVisited = false;
- }
- // Before backtracking, remove this node from the list of nodes visited
- // TODO
- if (nodeVisited == true){
- shortestDistance = shortestDistance - f.getDistance(node, node-1);
- currentPath.remove(currentPath.size()-1);
- }
- // Backtrack by returning so that you can try other paths
- return;
- }
- else{int next_node=0;
- for (node=0;node<currentPath.size();node++){
- // For loop over indices 0 through 6
- // If current index is in currentPath, skip it
- if (nodeVisited==false){
- next_node=node;
- }
- // 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