# Dijkstra Algorithm Implementation

Page 1 of 1

## 7 Replies - 2819 Views - Last Post: 06 December 2012 - 07:06 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=303048&amp;s=6878215b04018e132ef279248650bb7b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 The Helpless One

Reputation: 0
• 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>();
for (;;)/>/>
{
v = PriorityQueue.deleteMin(); //smallest unknown vertex
if ( v == null)
break;
v.known = true; // cost of the shortest path to vertex is found

{
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

• </luck>

Reputation: 293
• 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.

### #3 The Helpless One

Reputation: 0
• 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>();
while ( v = PriorityQueue.deleteMin() != null )
{
v.known = true; // cost of the shortest path to vertex is found

{
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?

### #4 Luckless

• </luck>

Reputation: 293
• 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?

### #5 The Helpless One

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

## Re: Dijkstra Algorithm Implementation

Posted 06 December 2012 - 06:49 PM

it doesn't apparently. haha.

### #6 Luckless

• </luck>

Reputation: 293
• 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

### #7 The Helpless One

Reputation: 0
• 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.

### #8 Luckless

• </luck>

Reputation: 293
• 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