[RobW1985]

Alright here's the deal, I did macosx's tutorial on Dijkstra's algorithm and got it to work but what was wondering if someone could explain something to me. When I first compiled this it wasn't giving me the correct answers for some reason, it was giving me a distance between two nodes as -2147483625. I went through the code trying to figure out why and changed things here and there to see if I could get it to work properly. Well I did and I don't know why my fix is working and the original is not. Here is my method for Dijkstra's which is basically the same one from the tutorial with minor changes to fit my code.

public int Dijkstra(GraphNode<T> start, GraphNode<T> end) {
		PriorityQueue<Edge<T>> heap = new PriorityQueue<Edge<T>>(25,new Comparator<Edge<T>>(){
			public int compare(Edge<T> first, Edge<T> second) {
				return (first.getWeight()+first.getOrigin().getDistance()) - (second.getWeight()+second.getOrigin().getDistance());
			}
		});
		resetDistances();
		start.setDistance(0);
		GraphNode<T> temp = start;
		resetVisited();
		do {
		LinkedList<Edge<T>> connectors = temp.edgeList;
		for(int i = 0; i < connectors.size(); i++) {
			Edge<T> edge = connectors.get(i);
			if (!edge.getDestination().getVisited()) {
				heap.add(edge);
			}
		}
		temp.setVisited(true);
		Edge<T> tempEdge = heap.poll();
		temp = tempEdge.getDestination();
		int distance = temp.distance;
		int newDistance = tempEdge.getOrigin().getDistance() + tempEdge.getWeight();
		
		if (newDistance < distance) 
			temp.setDistance(newDistance);
		
		} while (!heap.isEmpty());
		
		
		return end.getDistance();
	}
private void resetDistances() {
		for(int i = 0; i < nodeList.size(); i++) 
			nodeList.get(i).setDistance(Integer.MAX_VALUE);
		
	}
	private void resetVisited() {
		for (int i = 0; i < nodeList.size(); i++)
			nodeList.get(i).setVisited(false);
	}

The above code was tested on a graph with 7 nodes and the distance of the edges never exceeds 20, so it was a relatively small graph. When I put in 0 as my start and 1 or 2 as my end it returns the right number, If I start from anywhere else or end somewhere other than those 2 it returns the number -2147483625 or something very similar. It's kind of confusing me. However, in my resetDistances method if I change the value from Integer.MAX_VALUE to a smaller number like 20,000. The algorithm works when I test from any node to any node. My question is why will it work when I set all the graph nodes distance to 20,000 and not Integer.MAX_VALUE? From all the different articles I have read it seems I am supposed to set the distance to MAX_VALUE so why does it work like this? If you need my graphs or any other files let me know and I will be glad to post them.

This post has been edited by RobW1985: 22 August 2011 - 10:40 AM

[RobW1985]

Ok upon further testing I think I have a problem elsewhere, I tested this again with the 20000 as the value I am setting all my distances to and I noticed that when I go from a node in the end of the list to a node earlier in the list I am not getting the right answer, it just gives me 20,000. So every test where my starting location is greater than my ending location I am getting 20,000 as my answer but in the case where the start index is less than my end index it works perfectly fine

[macosxnerd101]

You're dealing with overflow there. When a value hits its MAX_VALUE, it circles back and starts at the MIN_VALUE.

[RobW1985]

ah Ok, thanks. Do you know why I'm hitting the MAX_VALUE, with the logic the way it is it shouldn't be adding numbers to MAX_VALUE and causing it to overflow, plus I'm still getting wrong numbers when I run the algorithm a certain way so I think I gotta do some work on it still, ill keep plugging away at it...

[RobW1985]

Update:
Ok I figured out what I was doing wrong. It was actually in my GraphNode class where I had the error. What I was doing was this

public void addEdge(GraphNode<T> other, int weight) {
		Edge<T> newEdge = new Edge<T>(this, other, weight);
		if(!edgeList.contains(newEdge))
			edgeList.add(newEdge);
		// if the graph is undirected, use this section of code, if it's directed, comment the next 3 lines out
		LinkedList<Edge<T>> edge = other.getEdgeList();
		if(!edge.contains(newEdge))
			edge.add(newEdge);

what this did is when I added an edge between A and B with weight 7, it set in A's edge list that A was the origin, B was the destination, and the weight is 7, then it added to B's edge list the same edge saying the origin was A and Destination B which is the opposite of what I wanted, the Origin should have been b and destination A, so I switched my code to this:

public void addEdge(GraphNode<T> other, int weight) {
		Edge<T> newEdge = new Edge<T>(this, other, weight);
		if(!edgeList.contains(newEdge))
			edgeList.add(newEdge);
		// if the graph is undirected, use this section of code, if it's directed, comment the next 3 lines out
		LinkedList<Edge<T>> edge = other.getEdgeList();
		Edge<T> otherEdge = new Edge<T>(other, this, weight); 
		if(!edge.contains(otherEdge))
			edge.add(otherEdge);

and now everything works fine the way it should

This post has been edited by RobW1985: 22 August 2011 - 11:52 AM

[macosxnerd101]

Awesome! Glad you got it resolved!