5 Replies - 1305 Views - Last Post: 22 August 2011 - 12:12 PM Rate Topic: -----

#1 RobW1985  Icon User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 38
  • Joined: 22-June 11

Question about Dijkstra's Algorithm

Posted 22 August 2011 - 10:39 AM

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


Is This A Good Question/Topic? 0
  • +

Replies To: Question about Dijkstra's Algorithm

#2 RobW1985  Icon User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 38
  • Joined: 22-June 11

Re: Question about Dijkstra's Algorithm

Posted 22 August 2011 - 11:00 AM

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
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10806
  • View blog
  • Posts: 40,279
  • Joined: 27-December 08

Re: Question about Dijkstra's Algorithm

Posted 22 August 2011 - 11:09 AM

You're dealing with overflow there. When a value hits its MAX_VALUE, it circles back and starts at the MIN_VALUE. :)
Was This Post Helpful? 1
  • +
  • -

#4 RobW1985  Icon User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 38
  • Joined: 22-June 11

Re: Question about Dijkstra's Algorithm

Posted 22 August 2011 - 11:18 AM

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...
Was This Post Helpful? 0
  • +
  • -

#5 RobW1985  Icon User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 38
  • Joined: 22-June 11

Re: Question about Dijkstra's Algorithm

Posted 22 August 2011 - 11:52 AM

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

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10806
  • View blog
  • Posts: 40,279
  • Joined: 27-December 08

Re: Question about Dijkstra's Algorithm

Posted 22 August 2011 - 12:12 PM

Awesome! Glad you got it resolved! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1