[The Helpless One]

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.

[Luckless]

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.

[The Helpless One]

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?

[Luckless]

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?

[The Helpless One]

it doesn't apparently. haha.

[Luckless]

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

[The Helpless One]

yea. thanks for all your help so far. Looks like this is going to be a ... all nighter.

[Luckless]

unfortunately, I need to hit the sack. Best of luck