• (2 Pages)
• • 1
• 2

## Data Structures: Dijkstra's Algorithm Rate Topic:     1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=203665&amp;s=4945f923576da0197e4a47ddf8b61170&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12764
• Posts: 45,948
• Joined: 27-December 08

Posted 04 December 2010 - 08:18 PM

I have deprecated this tutorial. Please see this link for my updated, more comprehensive tutorial.

Dijkstra's Algorithm is a graph-search algorithm that finds the shortest path between two Vertices on a weighted Graph. For Dijkstra's algorithm, we assume that all distances are positive.

So how exactly does this algorithm work? Basically, we initialize all the distances to infinity, except for the root Vertex which is initialized to 0. We then traverse the Graph from the starting point towards the end point. When we hit a Node, we evaluate the cumulative distance to that Node, which means the distance recorded at the previous Node plus to the distance to the current Node. So if we have A-->B weighted at 5 and B-->C weighted at C, B would record the distance 5, and C would record the distance 8. The reason we initialize to infinity is that the first time we hit that Node, everything will be less than infinity so the first distance will be stored at that Node.

For the purpose of this tutorial, I've set up a class to handle evaluating Dijkstra's algorithm using my Graph implementation from my Graphs Tutorial. I used Integer.MAX_VALUE as my infinity marker.
```import java.util.*;

/**
* A utility class to implement Dijkstra's algorithm
* @param E: The type to store in the Graph
* */
public class Dijkstra<E> {

//the Graph to traverse
private Graph<E> graph;

//the PriorityQueue for the heap-based sort
private PriorityQueue<Connector<E>> heap;

/**
* @param graph: The Graph to traverse
*
* The constructor initializes each Node's
* distance to Integer.MAX_VALUE, as the infinity value.
* When the weights are compared, they are initially compared
* to MAX_VALUE, which they will be less than.
* */
public Dijkstra(Graph<E> graph){
this.graph = graph;
resetGraph();
heap = new PriorityQueue<Connector<E>>(25, new Comparator<Connector<E>>(){
public int compare(Connector<E> one, Connector<E> two){
return (one.getDistance() + one.getOne().getDistance()) -
(two.getDistance() + two.getOne().getDistance());
}
});

}

//initializes the Graph Nodes to infinity
public void resetGraph(){
for(int i = 0; i < this.graph.count(); i++){
this.graph.get(i).setDistance(Integer.MAX_VALUE);
}
}

```

In this implementation of Dijkstra's algorithm, I'm using a naive, unamoritzed implementation. It comes down to basically a recursive depth-first search, updating distances for the Nodes. The minimum distance is found, and returned. Because all paths are evaluated naievely, the runtime of this implementation is O(V2), where v is the number of vertices in the Graph.
```
/**
* @param start: The Node to start from
* @param end: The target Node
* @param dist: The cumulative distance at this point
*
* This method is implemented recursively, finding the distance of
* the shortest path from some starting Node to the ending Node.
* I utilize Tree-recursion, comparing the results of the child calls
* to get a shortest distance.
* */
public int nonheapPath(Edge<E> start, Edge<E> end, int dist){

//set the weight to a maximum that every other weight has to
//be less than
int weight = Integer.MAX_VALUE;

//if we're at the end Node, stop
if(start == end)
return dist;

//for each child Node from start
for(int i = 0; i < connections.size(); i++){

Connector<E> temp = connections.get(i);
Edge<E> update = temp.getTwo();

//check to see if the new distance is shorter than the current one
if(update.getDistance() > (dist + temp.getDistance())){

//and update it if it is
update.setDistance(dist + temp.getDistance());
}

//now compare the current distance to the rest of the weights returned
//by child calls. Note the depth-first traversal here
weight = Math.min(weight, nonheapPath(update, end, update.getDistance()));

}
return weight;
}

```

This implementation of Dijkstra's algorithm is optimized and utilizes a greedy approach. The minimal paths are pushed onto a PriorityQueue, giving us a better idea of which path to evaluate next based on which has the lowest cost. We begin at the starting Node, which is initialized to a distance of 0. We then push its children onto the PriorityQueue, and poll the next one to evaluate, utilizing a breadth-first search over a depth-first search. We also do not need to store or evaluate minimum weights as we did in the previous version, as when the PriorityQueue is empty, the Graph will have been fully evaluated, and end will have the shortest distance to it, which we can return. Based on this optimization, the runtime improves from O(V2) to O(E log(V)), where E is the number of Edges (or Connectors) in the Graph.
```    /***
* @param start: The starting point
* @param end: The ending point
* @return int: The shortest distance from start to end
*
* This method uses a PriorityQueue to determine which Edge
* to visit next. Nodes are evaluated in a breadth-first search,
* and pushed onto the PriorityQueue. The PriorityQueue is then polled
* and the process is repeated until the PriorityQueue is empty.
* */
public int heapPath(Edge<E> start, Edge<E> end){
start.setDistance(0); //initialize the start distance to 0

//the Edge to evaluate. We evaluate the start Node first
Edge<E> evaluate = start;

//as long as we have elements in the Graph to traverse
do{

//push evaluate's children onto the PriorityQueue
Iterator<Connector<E>> iterate = connections.iterator();

while(iterate.hasNext()){
}

//then poll the PriorityQueue to determine
//which Node to visit next
Connector<E> temp = heap.poll();
evaluate = temp.getTwo();

//and update that Node's distance if a shorter path is found
int distance = evaluate.getDistance();
int newDist = temp.getOne().getDistance() + temp.getDistance();

if(newDist < distance)
evaluate.setDistance(newDist);

} while (!heap.isEmpty());

return end.getDistance();
}

```

If you want a test Graph to set this up with, I have gone ahead and set up the Graph to match the animation on Wikipedia.
```
/**
* Below, I set up the Graph on Wikipedia: http://en.wikipedia.org/wiki/Dijkstra's_Algorithm
* */
public static void main(String[] args){
Graph<Integer> list = new Graph<Integer>();
Edge<Integer> i = new Edge<Integer>(1, 0);
Edge<Integer> j = new Edge<Integer>(2, 0);
Edge<Integer> k = new Edge<Integer>(3, 0);
Edge<Integer> l = new Edge<Integer>(4, 0);
Edge<Integer> m = new Edge<Integer>(5, 0);
Edge<Integer> n = new Edge<Integer>(6, 0);

i.connectTo(j, 7);
i.connectTo(k, 9);
i.connectTo(n, 14);

j.connectTo(k, 10);
j.connectTo(l, 15);

k.connectTo(n, 2);
k.connectTo(l, 11);

l.connectTo(m, 6);
n.connectTo(m, 9);

Dijkstra<Integer> test = new Dijkstra<Integer>(list);

}
}

```

Is This A Good Question/Topic? 3

## Replies To: Data Structures: Dijkstra's Algorithm

### #2 lesley^^ Reputation: 0
• Posts: 1
• Joined: 05-December 10

Posted 05 December 2010 - 03:51 AM

what's this called "}" ?

can java beans be a part of vb code?

### #3 DADDYCARDONA Posted 05 December 2010 - 04:55 AM lesley^^, on 05 December 2010 - 02:51 AM, said:

what's this called "}" ?

can java beans be a part of vb code?

"{" and "}" are called curly braces.

### #4 EnvXOwner Reputation: 358
• Posts: 2,319
• Joined: 10-August 09

Posted 05 December 2010 - 06:20 AM lesley^^, on 05 December 2010 - 04:51 AM, said:

what's this called "}" ?

can java beans be a part of vb code?

Braces. Great tutorial macosxnerd101.
I think that you should start out with a more simple tutorial. So you understand more of what he is coding.

This post has been edited by EnvXOwner: 05 December 2010 - 10:32 AM

### #5 skorned Reputation: 13
• Posts: 41
• Joined: 30-August 08

Posted 05 December 2010 - 09:14 AM

Hey nice tutorial. I've wanted to implement Dijkstra's algorithm for a while, and also be able to pronounce it. Still need help on the latter, but I'll get there eventually.

Meanwhile, quick typo spot: macosxnerd101, on 04 December 2010 - 07:18 PM, said:

and B-->C weighted at C

Here, the second C should be 3 right?

### #6 SpeedisaVirus Reputation: 115
• Posts: 855
• Joined: 06-October 08

Posted 05 December 2010 - 09:25 AM

Netbeans is a Java IDE. Java beans are reusable code components.

### #7 Ronald91 Reputation: 11
• Posts: 31
• Joined: 26-April 09

Posted 05 December 2010 - 09:35 AM

This is a great tutorial and I think I understand the gist of it, however, when I try to run the code in Eclipse I get a boatload of errors. All the errors stem from these three errors, "Graph cannot be resolved to a type", "Connector cannot be resolved to a type", "Edge cannot be resolved to a type". How can I solve this?

### #8 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12764
• Posts: 45,948
• Joined: 27-December 08

Posted 05 December 2010 - 09:39 AM

@skorned: The Connector between B and C is weighted at 3, but the total distance from A to C is 8, so that's why it is weighted at 8. As we traverse the Graph, the cumulative distance to a point is recorded as the distance at that point.

@Ronald91: I used my Graph implementation from my Graphs tutorial, linked in my first post. ### #9 Ronald91 Reputation: 11
• Posts: 31
• Joined: 26-April 09

Posted 05 December 2010 - 09:47 AM

### #10 peterjdickson Posted 24 June 2011 - 06:11 PM

Hello, I loaded up your sample classes (verbatim) and attempted to execute the heapPath solution to your Wiki sample graph.

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:2760)
at java.util.Arrays.copyOf(Arrays.java:2734)
at java.util.PriorityQueue.grow(PriorityQueue.java:238)
at java.util.PriorityQueue.offer(PriorityQueue.java:269)
at dijkstra.Dijkstra.heapPath(Dijkstra.java:112)
at dijkstra.Main.main(Main.java:43)

Any suggestions? Thanks! I can post my test of your sample if you would like!

### #11 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12764
• Posts: 45,948
• Joined: 27-December 08

Posted 24 June 2011 - 06:25 PM

I just ran that code and it worked fine. Which two nodes are you trying to find the distance for? Also, post the code.

### #12 peterjdickson Posted 24 June 2011 - 06:44 PM

Didn't realize it was PM. I'll repost. With code.

### #13 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12764
• Posts: 45,948
• Joined: 27-December 08

Posted 24 June 2011 - 06:45 PM

It's not PM. That's just my signature. ### #14 peterjdickson Posted 24 June 2011 - 06:56 PM

Attached is the code! Thanks for taking a look as quickly as you have.

Note that i'm trying to solve from i to m :

test.heapPath(i, m);

### #15 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12764
• Posts: 45,948
• Joined: 27-December 08

Posted 24 June 2011 - 06:59 PM

I just ran that and got 20 as the result. To confirm, this is the code copied verbatim from the tutorial. Have you modified the Graph at all? Other parts of the code? There is no way what I have could produce an OutOfMemoryError unless you have reduced the heap size for the JVM on your computer.
```/***
* @param start: The starting point
* @param end: The ending point
* @return int: The shortest distance from start to end
*
* This method uses a PriorityQueue to determine which Edge
* to visit next. Nodes are evaluated in a breadth-first search,
* and pushed onto the PriorityQueue. The PriorityQueue is then polled
* and the process is repeated until the PriorityQueue is empty.
* */
public int heapPath(Edge<E> start, Edge<E> end){
start.setDistance(0); //initialize the start distance to 0

//the Edge to evaluate. We evaluate the start Node first
Edge<E> evaluate = start;

//as long as we have elements in the Graph to traverse
do{

//push evaluate's children onto the PriorityQueue
Iterator<Connector<E>> iterate = connections.iterator();

while(iterate.hasNext()){
}

//then poll the PriorityQueue to determine
//which Node to visit next
Connector<E> temp = heap.poll();
evaluate = temp.getTwo();

//and update that Node's distance if a shorter path is found
int distance = evaluate.getDistance();
int newDist = temp.getOne().getDistance() + temp.getDistance();

if(newDist < distance)
evaluate.setDistance(newDist);

} while (!heap.isEmpty());

return end.getDistance();
}

```

• (2 Pages)
• • 1
• 2

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }