• (2 Pages)
  • +
  • 1
  • 2

Data Structures: Dijkstra's Algorithm Rate Topic: ***** 1 Votes

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • Joined: 27-December 08

Posted 04 December 2010 - 08:18 PM

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){
        LinkedList<Connector<E>> connections = start.getConnections();

        //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
            LinkedList<Connector<E>> connections = evaluate.getConnections();
            Iterator<Connector<E>> iterate = connections.iterator();

            while(iterate.hasNext()){
                heap.add(iterate.next());
            }

            //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);

        list.addEdge(i);
        list.addEdge(j);
        list.addEdge(k);
        list.addEdge(l);
        list.addEdge(m);
        list.addEdge(n);
        
        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^^  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#3 DADDYCARDONA  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 67
  • Joined: 04-July 10

Posted 05 December 2010 - 04:55 AM

View Postlesley^^, 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.

Yes I knew an answer.!
Was This Post Helpful? 0
  • +
  • -

#4 EnvXOwner  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 357
  • View blog
  • Posts: 2,319
  • Joined: 10-August 09

Posted 05 December 2010 - 06:20 AM

View Postlesley^^, 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

Was This Post Helpful? 1
  • +
  • -

#5 skorned  Icon User is offline

  • New D.I.C Head

Reputation: 13
  • View blog
  • 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:

View Postmacosxnerd101, on 04 December 2010 - 07:18 PM, said:

and B-->C weighted at C


Here, the second C should be 3 right?
Was This Post Helpful? 0
  • +
  • -

#6 SpeedisaVirus  Icon User is offline

  • Baller
  • member icon

Reputation: 114
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Posted 05 December 2010 - 09:25 AM

Netbeans is a Java IDE. Java beans are reusable code components.
Was This Post Helpful? 0
  • +
  • -

#7 Ronald91  Icon User is offline

  • New D.I.C Head

Reputation: 11
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#9 Ronald91  Icon User is offline

  • New D.I.C Head

Reputation: 11
  • View blog
  • Posts: 31
  • Joined: 26-April 09

Posted 05 December 2010 - 09:47 AM

Whoa, bad reading on my part lol and thanks.
Was This Post Helpful? 0
  • +
  • -

#10 peterjdickson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-June 11

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 java.util.PriorityQueue.add(PriorityQueue.java:251)
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!
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • 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.
Was This Post Helpful? 0
  • +
  • -

#12 peterjdickson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-June 11

Posted 24 June 2011 - 06:44 PM

Didn't realize it was PM. I'll repost. With code.
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • Joined: 27-December 08

Posted 24 June 2011 - 06:45 PM

It's not PM. That's just my signature. :)
Was This Post Helpful? 0
  • +
  • -

#14 peterjdickson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-June 11

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);
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • 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
        LinkedList<Connector<E>> connections = evaluate.getConnections();
        Iterator<Connector<E>> iterate = connections.iterator();

        while(iterate.hasNext()){
            heap.add(iterate.next());
        }

        //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();
}


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2