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:
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?
Please help, I feel so stupid.