7 Replies - 1353 Views - Last Post: 06 December 2012 - 07:06 PM Rate Topic: -----

#1 The Helpless One  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-December 12

Dijkstra Algorithm Implementation

Posted 06 December 2012 - 05:43 PM

Hello. First time poster. Anyhow I'm having trouble implementing this certain type of Dijkstra algorithm.
Here's the algorithm that I'm supposed to use.
void dijksra(Vertex start)
{
for each Vertex v in V {
v.dist = Integer.MAX_VALUE;
v.known = false;
v.path = null;
}

start.distance = 0;

while there are unknown vertices {
v = unknown vertex with smallest distance
v.known = true;
for each Vertex w adjacent to v
if (!w.known)
if (v.dist + weight(v, w)< w.distance){
decrease(w.dist to v.dist+weight(v, w))
w.path = v;
}
}

}



And here's what I have so far.
void Dijkstra(Vertex src) // create dijkstra class
{
	Vertex v,w;
    src.dist = 0; 
    // create PriorityQueue
    PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
    queue.add(src);
    for (;;)/>/>
    {
    	v = PriorityQueue.deleteMin(); //smallest unknown vertex
    	if ( v == null)
    		break;
    	v.known = true; // cost of the shortest path to vertex is found
    	
   
    for (w.adj: v.adj) // adjacency list
    {
    	if (!w.known)	// another shorter path might still be found
    		if (v.dist + cost(v,w) < w.dist)
    		{
    			w.dist = (v.dist + cost(v,w));
    			w.path = v;	// shortest path
    		}
    }
    }
}


So the question is am I on the right track for implementing this algorithm and if not, any ideas of what I could change? Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Dijkstra Algorithm Implementation

#2 Luckless  Icon User is offline

  • </luck>
  • member icon

Reputation: 292
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:37 PM

Your loop structure isn't good. You should never have it loop forever and depend on the if/break combination to terminate it. try:

while((v = PriorityQueue.deleteMin()) != null){
// rest of code here.
}



This checks the condition for termination before looping again and is a much "safer" design since it relies on the while loop's built in conditional check instead of an infinite for loop.
Was This Post Helpful? 1
  • +
  • -

#3 The Helpless One  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-December 12

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:41 PM

Got it. Here's what I have so far
void Dijkstra(Vertex src) // create Dijkstra class
{
	Vertex v,w;  // 
	src.dist = 0; // set source at starting point 
	// create PriorityQueue
	PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
	queue.add(src);
	 while ( v = PriorityQueue.deleteMin() != null )	   
	{
	    v.known = true; // cost of the shortest path to vertex is found

	   for (  Edge e : v.adj) // adjacency list
	    {
	    	double cvw = e.cost;
	    	if (!w.known)	// another shorter path might still be found
	    		if (v.dist + cvw < w.dist)
	    		{
	    			w.dist = (v.dist + cvw);
	    			w.path = v;	// shortest path
	    		}
	    }
	 }
	
}



and I have another problem which is that deleteMin is undefined for PriorityQueue. Anyway I can get around that?
Was This Post Helpful? 0
  • +
  • -

#4 Luckless  Icon User is offline

  • </luck>
  • member icon

Reputation: 292
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:48 PM

You need to use your instance "queue". Remember that this is your object/instance defined by the PriorityQueue class. I don't see that method for PriorityQueue. What you need to do is check out how to use a Comparator to dictate what priority is. My next question is, how does adding src to the queue get you all the vertices?
Was This Post Helpful? 0
  • +
  • -

#5 The Helpless One  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-December 12

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:49 PM

it doesn't apparently. haha.
Was This Post Helpful? 0
  • +
  • -

#6 Luckless  Icon User is offline

  • </luck>
  • member icon

Reputation: 292
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:56 PM

Ok, let me direct you to some tutorials that you can take or leave. To be honest, I suck with graph algorithms unless I stare at it for a good long time:

http://www.vogella.c...ra/article.html

http://www.algolist.com/code/java/Dijkstra's_algorithm

This second one looks a lot like what you are trying to do =) Might start there
Was This Post Helpful? 0
  • +
  • -

#7 The Helpless One  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-December 12

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:57 PM

yea. thanks for all your help so far. Looks like this is going to be a ... all nighter.
Was This Post Helpful? 0
  • +
  • -

#8 Luckless  Icon User is offline

  • </luck>
  • member icon

Reputation: 292
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 07:06 PM

unfortunately, I need to hit the sack. Best of luck
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1