Help with a Graph Data Structure and the Shortest Path

[rhm54]

Alright before I begin, let me be clear I am very green to Java and programming in general. I am taking this class online, and I am having a very hard time. The professor will not actually teach which makes this very very hard for me. When I ask him for help he will either A. send me website links that have very little to do with my actual question or B. Tell me to read the textbook. But, even doing all that he says to do the textbook doesn't explain everything how I can understand it and the links are vague. So in short I need help.

I have been tasked with making a navigation system that will prompt a user for a starting and ending city and then report back the shortest path. I thought I was getting close but I realized that my plan had two major flaws. Here is the code so far

import java.util.*;


public class NavigationSystem {
	
	private Node myGraph[];	
	private String citylist[] = {"Birmingham", "Tuscaloosa", "Atlanta", "Montgomery", "Macon", "Mobile", "Tallahassee", "Ashburn", "Lake City", "Ocala", "Orlando", "Daytona Beach", "Jacksonville", "Savannah"};
	
	//Build the Graph
	public NavigationSystem(){
		for(int i = 0; i < citylist.length; i++){
			myGraph[i] = new Node(citylist[i], 0, null);
	}
		//Setting up the children of Birmingham
		Node temp = myGraph[0];
		temp.setPointer(new Node("Tuscaloosa", 58, null));
		temp = temp.getPointer();
		temp.setPointer(new Node("Montgomery", 90, null));
		temp = temp.getPointer();
		temp.setPointer(new Node("Atlanta", 146, null));
		
		//Setting up the children of Tuscaloosa
		temp = myGraph[1];
		temp.setPointer(new Node("Birmingham", 58, null));
		
		//Setting up the children of Atlanta
		temp = myGraph[2];
		temp.setPointer(new Node("Macon", 84, null));
		temp =  temp.getPointer();
		temp.setPointer(new Node("Birmingham", 146, null));
		temp = temp.getPointer();
		temp.setPointer(new Node("Montgomery", 161, null));
		
		//Setting up the children of Montgomery
		temp = myGraph[3];
		temp.setPointer(new Node(citylist[0], 90, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[2], 161, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[5], 170, null));
		
		//Setting up the children of Macon
		temp = myGraph[4];
		temp.setPointer(new Node(citylist[2], 84, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[7], 84, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[13], 165, null));
		
		//Setting up the children of Mobile
		temp = myGraph[5];
		temp.setPointer(new Node(citylist[3], 170, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[6], 243, null));
		
		//Setting up the children of Tallahassee
		temp = myGraph[6];
		temp.setPointer(new Node(citylist[8], 111, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[5], 243, null));
		
		//Setting up the children of Ashburn
		temp = myGraph[7];
		temp.setPointer(new Node(citylist[4], 84, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[8], 130, null));
		
		//Setting up the children of Lake City
		temp = myGraph[8];
		temp.setPointer(new Node(citylist[12], 64, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[9], 83, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[6], 111, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[7], 130, null));
		
		//Setting up the children of Ocala
		temp = myGraph[9];
		temp.setPointer(new Node(citylist[10], 80, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[8], 83, null));
		
		//Setting up the children of Orlando
		temp = myGraph[10];
		temp.setPointer(new Node(citylist[11], 55, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[9], 80, null));
		
		//Setting up the children of Daytona Beach
		temp = myGraph[11];
		temp.setPointer(new Node(citylist[10], 55, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[12], 93, null));
		
		//Setting up the children of Jacksonville
		temp = myGraph[12];
		temp.setPointer(new Node(citylist[8], 64, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[11], 93, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[13], 139, null));
		
		//Setting up the children of Savannah
		temp = myGraph[13];
		temp.setPointer(new Node(citylist[12], 139, null));
		temp = temp.getPointer();
		temp.setPointer(new Node(citylist[4], 165, null));
		
	}
	
	public int findPosition(String s){
		//Cycle through the city list and find the location of the start city
		int position = -1;
		for(int i = 0; i < citylist.length; i++){
			if(myGraph[i].getCity() == s){
				position = i;
				break;
			}
		}
		return position;
	}
	
	public int DFS(String Start, String End){
		int startposition = findPosition(Start);
		int currentpath = 0;
		int bestpath = 0;
		String current, best, tempstring;
		Node travelnode, tempnode;
		Stack DFSstack = new Stack();
		ArrayList<String> closedlist = new ArrayList<String>();
		
		//Expanding the start position to the stack, adding it to the closedlist.
		travelnode = myGraph[startposition];
		closedlist.add(travelnode.getCity());
		while(travelnode.getPointer() != null){
			travelnode = travelnode.getPointer();
			DFSstack.add(travelnode);
		}
		
		//Cycling through all the edges using a stack
		while(!DFSstack.isEmpty()){
		tempnode = (Node)DFSstack.peek();
		currentpath += tempnode.getDistance();
		if(!closedlist.contains(tempnode.getCity())){
			tempstring = tempnode.getCity();
			travelnode = myGraph[findPosition(tempstring)];
			closedlist.add(travelnode.getCity());  //Adding the city to the closedlist
			while(travelnode.getPointer() != null){
				travelnode = travelnode.getPointer();
				DFSstack.add(travelnode);
			}
			DFSstack.pop();
		}
		else
			DFSstack.pop();
			currentpath -= tempnode.getDistance();//removes the distance if we have to backtrack
	}
	}
	public class Node{
		int distance;
		String City;
		Node pointer;
		
		 public Node(String s, int i, Node n ){
			pointer=n;
			City=s;
			distance=i;
		}
		 public Node(String s){
			 pointer=null;
			 City=s;
			 distance=0;
		 }
		public int getDistance() {
			return distance;
		}
		public void setDistance(int distance) {
			this.distance = distance;
		}
		public String getCity() {
			return City;
		}
		public void setCity(String city) {
			City = city;
		}
		public Node getPointer() {
			return pointer;
		}
		public void setPointer(Node pointer) {
			this.pointer = pointer;
		}
	}
		
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

Here is the problem. I have it set up now to only push the nodes to a stack if the node has not been expanded before, to prevent it from running forever. I didn't see this problem until after I had it in place but the problem is that if I am trying to find the best route from Birmingham to Mobile for example the code will do the following:

Expand Birmingham
Push - 146 Atlanta, 90 Montgomery, 58 Tuscaloosa to the Stack
Add Birmingham to the closed list

Expand Atlanta
Push - 161 Montgomery, 146 Birmingham, 84 Macon to the Stack
Add Atlanta to the Closed list
Pop 146 Atlanta from the Stack

Expand Montgomery
Push- 170 Mobile, 161 Atlanta, 90 Birmingham to the Stack
Add Montgomery to the closed list
Pop 161 Montgomery from the stack

The problem I see here is that with the next step we will have found one route to Mobile(Birmingham - Atlanta - Montgomery - Mobile) but we will have destroyed the edge connecting mobile and montgomery. So, even though the best route is from Birmingham - Montgomery - Mobile, we will never find it. The other problem is when I reach a point in the graph where I have already added the distance from say Atlanta to Macon and I have already expanded Ashburn and Savannah, how can I tell the program to remove the distance from Atlanta to Macon when I have already poppped the node that contains that data?:confused:

Please help, I feel so stupid.

[hardwired]

import java.util.*;

public class NavTest2 {
    private Node[] graph;
    private String[] citylist = {
        "Birmingham", "Tuscaloosa", "Atlanta", "Montgomery", "Macon",
        "Mobile", "Tallahassee", "Ashburn", "Lake City", "Ocala",
        "Orlando", "Daytona Beach", "Jacksonville", "Savannah"
    };
	
    //Build the Graph
    public NavTest2() {
        graph = new Node[citylist.length];
        for(int i = 0; i < citylist.length; i++) {
            graph[i] = new Node(citylist[i], 0, null);
        }
        //Setting up the children of Birmingham
        Node temp = graph[0];
        temp.setPointer(new Node("Tuscaloosa", 58, null));
        temp = temp.getPointer();
        temp.setPointer(new Node("Montgomery", 90, null));
        temp = temp.getPointer();
        temp.setPointer(new Node("Atlanta", 146, null));

        //Setting up the children of Tuscaloosa
        temp = graph[1];
        temp.setPointer(new Node("Birmingham", 58, null));

        //Setting up the children of Atlanta
        temp = graph[2];
        temp.setPointer(new Node("Macon", 84, null));
        temp =  temp.getPointer();
        temp.setPointer(new Node("Birmingham", 146, null));
        temp = temp.getPointer();
        temp.setPointer(new Node("Montgomery", 161, null));

        //Setting up the children of Montgomery
        temp = graph[3];
        temp.setPointer(new Node(citylist[0], 90, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[2], 161, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[5], 170, null));

        //Setting up the children of Macon
        temp = graph[4];
        temp.setPointer(new Node(citylist[2], 84, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[7], 84, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[13], 165, null));

        //Setting up the children of Mobile
        temp = graph[5];
        temp.setPointer(new Node(citylist[3], 170, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[6], 243, null));

        //Setting up the children of Tallahassee
        temp = graph[6];
        temp.setPointer(new Node(citylist[8], 111, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[5], 243, null));

        //Setting up the children of Ashburn
        temp = graph[7];
        temp.setPointer(new Node(citylist[4], 84, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[8], 130, null));

        //Setting up the children of Lake City
        temp = graph[8];
        temp.setPointer(new Node(citylist[12], 64, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[9], 83, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[6], 111, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[7], 130, null));

        //Setting up the children of Ocala
        temp = graph[9];
        temp.setPointer(new Node(citylist[10], 80, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[8], 83, null));

        //Setting up the children of Orlando
        temp = graph[10];
        temp.setPointer(new Node(citylist[11], 55, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[9], 80, null));

        //Setting up the children of Daytona Beach
        temp = graph[11];
        temp.setPointer(new Node(citylist[10], 55, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[12], 93, null));

        //Setting up the children of Jacksonville
        temp = graph[12];
        temp.setPointer(new Node(citylist[8], 64, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[11], 93, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[13], 139, null));

        //Setting up the children of Savannah
        temp = graph[13];
        temp.setPointer(new Node(citylist[12], 139, null));
        temp = temp.getPointer();
        temp.setPointer(new Node(citylist[4], 165, null));
    }

    private List<String> getShortestRoute(Node origin, Node dest) {
        List<List<String>> routes = findRoutes(origin, dest);
        int minDist = Integer.MAX_VALUE;
        int index = -1;
        for(int i = 0; i < routes.size(); i++) {
            List<String> list = routes.get(i);
            int distance = getDistance(list.toArray(new String[list.size()]));
            if(distance < minDist) {
                minDist = distance;
                index = i;
            }
            //System.out.printf("route distance is %3d for %s%n",
            //                   distance, list);
        }
        List<String> shortest = routes.get(index);
        System.out.println("----------------------");
        System.out.printf("shortest route = %s%n with distance = %d%n",
                           shortest, minDist);
        System.out.println("----------------------");
        return shortest;
    }

    private int getDistance(String[] cities) {
        int totalDistance = 0;
        for(int i = 0; i < cities.length-1; i++) {
            Node node = getNode(cities[i]);
            int distance = getDistanceTo(node, cities[i+1]);
            totalDistance += distance;
        }
        return totalDistance;
    }

    private int getDistanceTo(Node node, String city) {
        Node[] pointers = getPointers(node);
        for(int i = 0; i < pointers.length; i++) {
            Node pointer = pointers[i];
            if(pointer.getCity().equals(city))
                return pointer.getDistance();
        }
        return 0;
    }

    private List<List<String>> findRoutes(Node origin, Node dest) {
        List<List<String>> allRoutes = new ArrayList<List<String>>();
        Node[] pointers = getPointerNodes(origin);
        for(int i = 0; i < pointers.length; i++) {
            List<String> list = new ArrayList<String>();
            list.add(origin.getCity());
            list.add(pointers[i].getCity());
            List<List<String>> routes = findRoute(list, pointers[i], dest);
            for(int j = 0; j < routes.size(); j++) {
                allRoutes.add(routes.get(j));
            }
        }
        return allRoutes;
    }

    private List<List<String>> findRoute(List<String> list, Node from, Node to) {
        List<List<String>> results = new ArrayList<List<String>>();
        if(from.getCity().equals(to.getCity()))
            results.add(list);
        List<List<String>> lists = addPointer(list, from, to);

        boolean haveMore = true;
        do {
            List<List<String>> subList = new ArrayList<List<String>>();
            for(int i = 0; i < lists.size(); i++) {
                haveMore = false;
                List<String> next = lists.get(i);
                String lastItem = next.get(next.size()-1);
                Node n = getNode(lastItem);
                List<List<String>> nextLists = addPointer(next, n, to);
                if(nextLists != null) {
                    for(int j = 0; j < nextLists.size(); j++) {
                        next = nextLists.get(j);
                        if(next.get(next.size()-1).equals(to.getCity())) {
                            results.add(next);
                            haveMore = false;
                            break;
                        }
                        subList.add(nextLists.get(j));
                    }
                }
            }
            if(subList.size() > 0) {
                lists = subList;
                haveMore = true;
            }
        } while(haveMore);

        return results;
    }

    private List<List<String>> addPointer(List<String> list,
                                          Node from, Node to) {
        List<List<String>> lists = new ArrayList<List<String>>();
        if(from.getCity().equals(to.getCity()))
            lists.add(list);
        Node[] pointers = getPointerNodes(from);
        for(int i = 0; i < pointers.length; i++) {
            List<String> next = new ArrayList<String>(list);
            String nextCity = pointers[i].getCity();
            if(list.contains(nextCity))
                continue;
            next.add(nextCity);
            lists.add(next);
        }
        return (lists.size() != 0) ? lists : null;
    }

    private Node[] getPointerNodes(Node node) {
        List<Node> list = new ArrayList<Node>();
        String city = node.getCity();
        for(int i = 0; i < graph.length; i++) {
            Node next = graph[i];
            Node pointer = next.getPointer();
            while(pointer != null) {
                if(pointer.getCity().equals(city))
                    list.add(next);
                pointer = pointer.getPointer();
            }
        }
        return list.toArray(new Node[list.size()]);
    }

    private Node[] getPointers(Node node) {
        List<Node> list = new ArrayList<Node>();
        Node pointer = node.getPointer();
        while(pointer != null) {
            list.add(pointer);
            pointer = pointer.getPointer();
        }
        return list.toArray(new Node[list.size()]);
    }

    private Node getNode(String city) {
        for(int i = 0; i < graph.length; i++) {
            if(graph[i].getCity().equals(city))
                return graph[i];
        }
        return null;
    }

    public class Node {
        int distance;
        String City;
        Node pointer;

        public Node(String s, int i, Node n) {
            pointer=n;
            City=s;
            distance=i;
        }

        public Node(String s) {
            this(s, 0, null);
        }

        public int getDistance() { return distance; }

        public void setDistance(int distance) { this.distance = distance; }

        public String getCity() { return City; }

        public void setCity(String city) { City = city; }

        public Node getPointer() { return pointer; }

        public void setPointer(Node pointer) { this.pointer = pointer; }

        public String toString() {
            String point = (pointer != null) ? " pointer:" + pointer
                                             : "";
            String dist = (distance != 0) ? " distance:" + distance
                                          : "";
            return "Node[City:" + City + dist + point + "]";
        }
    }

    public static void main(String[] args) {
        // "Birmingham", "Tuscaloosa", "Atlanta", "Montgomery", "Macon",
        // "Mobile", "Tallahassee", "Ashburn", "Lake City", "Ocala",
        // "Orlando", "Daytona Beach", "Jacksonville", "Savannah"

        int[][] indices = {
            { 4, 6 }, { 6, 9 }, { 3, 11 }, { 8, 5 },
            { 3, 13 }, { 3, 9 }, { 12, 5 }, { 2, 4 }
        };
        NavTest2 test = new NavTest2();
        Node[] nodes = test.graph;
        for(int i = 0; i < indices.length; i++) {
            Node origin = nodes[indices[i][0]];
            Node dest = nodes[indices[i][1]];
            List<String> route = test.getShortestRoute(origin, dest);
            //System.out.printf("shortest route = %s%n", route);
        }
    }
}