Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Dijkstra's Algorithm in Java?

pseudocode shortest path

  • Please log in to reply
1 reply to this topic

#1 sam199006

sam199006

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 11 December 2011 - 08:18 AM

I have to make a java program that traverses a graph using Dijkstra's algorithm. I also have to use this program to simutaneously find the shortest path and shortest distance for a given destination.

I have it setup now so that the shortest path and shortest distance methods just return a list (declared at the start of the class) and an int (also declared at the start of the class), respectively, so all of the work is supposed to be done in the 'public void doDijkstra(T start)' method.

Can someone give me any help on how to accomplish this (like pseudocode, examples, etc.) I really need help since this is due tonight!!!

Below is a skeleton of what my idea is, Thanks!


dij is a boolean variable I am using as a 'flag' for another method.

the graph could be something like ABC with weights given so that A to B is '12', B to C is '5' and C to A is '2'
something, processed, shortpath are hashsets (when i return shortpath in the shortpath method, i cast it to (List<T>)
temp is a T variable which I plan on using to store the current node I am at, processed is to keep track of nodes i have reached, and something is just the list with all the nodes.
I'm not sure if a map is needed for this, but I have one anyway......

I know this is a mess, but like I said, I could really use a good example or pseudocode, I just want to know how to do this.


public void doDijkstra(T start) {
		dij = true;
		something.addAll(graph.getAllElements());
		processed.add(start);
		valueMap.put(start, 0);
		while(processed.containsAll(something)==false){
			temp = something.iterator().next();//WRONG!!!!!!!!
			processed.add(temp);
			while(graph.getNeighbors(temp).hasNext())
				if(        ){
					
					
					shortPath.add(temp);
				}
			}
		}

Edited by sam199006, 11 December 2011 - 08:51 AM.

  • 0

#2 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 766 posts
  • Programming Language:C, Java, PHP, JavaScript
  • Learning:PHP

Posted 11 December 2011 - 09:04 PM

Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005 - YouTube

Here's a very informative video on dijkstra's algorithm (with pseudo-code)

---------- Post added at 11:04 PM ---------- Previous post was at 10:41 PM ----------

As far as finding the shortest path (noting that the shortest path isn't always the fastest path), I'd set all the weights to 1 and re-run the dijsktra algorithm. This should get you the shortest path from node a to z.
As far as getting a list of the path, you'll need to keep a data structure, perhaps a map or an array, that keeps track of the previous vertex of a vertex. Every time you find/update an optimal distance for a vertex, you should note that vertex and it's previous vertex in the data structure.

Backtracking through the data structure should get you the path.

Anyone is welcome to correct me on this, as I'm not the greatest at graphs/graph theory.
  • 0





Also tagged with one or more of these keywords: pseudocode, shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download