Graphs and Dijkstra's algorithm Last update : 10/12/2002 back to HOME PAGE

I wrote this article in order to share the source-code of a basic implementation of the the Dijkstra's algorithm. Readers after full-featured, industrial-strength Java implementations of Dijkstra's shortest path algorithm should look into JGL and JDSL, among others (Thanks to Renaud Waldura for the links taken from his article).
  1. Context description
  2. Class Diagram
  3. Tutorial
  4. Download
  5. References
  6. Credits - about the author of this article and the license to respect if you want to use the code

Important : Update from the 04/03/2004 : there was a bug in the PriorityQueue class which was generated inaccurate results. I'd like to thank Olivier Daroux for telling me about the problem and fixing it. I have updated the source-code and it is available for download.

back to Top

1. Context description

If you are not familiar with graph theory, I suggest you to read a bit of literature about it see Links.

What is a weighted directed graph ?

A graph is a set of vertices, connected by edges.

In an directed graph, each edge has a direction (represented by an arrow).

In a weighted graph, each edge is assigned a weight. The weight can be assimilated to the distance between 2 vertices.

Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be formulated as questions about certain graphs. One of the best example is a railway network :

  • Each train station is a vertex
  • The railways between 2 stations are an edge
  • The distance between 2 train stations is equivalent to the weight

Typical problems which can be solved with graphs :

  • Shortest path problem
  • Route inspection problem (aka "Chinese Postman Problem")
  • Traveling salesman problem

The Dijkstra's algorithm


The Dijkstra's algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. All weights must be nonnegative. You can have a look to the formal definition of this algorithm if it can help you (it did not help me !).

Implementation in java

Let's define the following data structures :

	runAlgorihtm(Object sourceVertex, Object destinationVertex) {

        // Initialization, empty all data structures





        // add source vertex with a distance of 0

        shortestPathMap.put(sourceVertex, new Integer(0));

        // Insert source vertex with a distance of 0

        remainingVerticesQueue.insert(sourceVertex, 0);

        // While the priority queue is not empty

        while ( !remainingVerticesQueue.isEmpty() ) {

            // Sort the vertices in the Remaining vertices according to their distance from the source

            // and select the closest one (i.e. dequeue the element with the lowest priority in the queue)

            Object closest = remainingVerticesQueue.dequeueLowestPriorityElement();

            // if the destination is reached, stop the execution

            if ( closest.equals(destinationVertex) ) {



            //  Add the closest vertex to the determined Vertices set


            // Relaxation, see explanations below




The PriorityQueue

I have used a Priority Queue to solve the problem of finding the closest element. A Priority Queue is a collection of elements ordered by a priority (positive integer).

The relax method


     * The relaxation process updates the costs of all the vertices v connected to a vertex u


     * @param vertex whose adjacent's vertices should be relaxed


    private void relax(Object vertex) {

        // Iterate on adjacent vertices to the vertex which is relaxed

        Iterator adjacentVertices = graph.getAdjacentVertices(vertex);

        while (adjacentVertices.hasNext()) {

            Object adjVertex =;

            // Do not relax elements which are already determined

            if (!determinedVerticesSet.contains(adjVertex)) {

                // distance = shortest distance from source + distance(vertex, adjacent vertex)

                int distance = getShortestPathFromSource(vertex) +  graph.getEdgeWeight(vertex, adjVertex);

                // Have we found a shortest path ?

                if (getShortestPathFromSource(adjVertex) > distance) {

                    // update shortest path result map

                    setShortestPathFromStart(adjVertex, distance);

                    // update predessors map result

                    predecessorsMap.put(adjVertex, vertex);

                    // re-balance the remaining vertices according to the new shortest distance found

                    remainingVerticesQueue.insert(adjVertex, distance);



        } // end while


The best way to understand how the algorithm works is to have a look to the applet demo.

back to Top

2. Class Diagram

There is an IMAGE MAP on the diagram : click on a class to see its javadoc.

IGraph is the Interface which specifies a weighted oriented graph. All search algorithms and client classes use that Interface to deal with graphs. If the implementation changes, no change will be needed in the clients classes (that's the advantages of using Interfaces !).

AdjacencyMatrixGraph is an implementation of the graph using an adjacency matrix.

Path is a generalization of the route concept. It is a list of Objects ( i.e. O1--O2--O3--04). Cloneable.

PathFinder contains all the search methods.

Dijkstra is an implementation of the Dijkstra's algorithm to search for the shortest distance in a weighted graph

Dijkstra.PriorityQueue is a inner class of Dijkstra used by the Dijkstra's algorithm to choose the closest vertex (the one whose priority is the lowest )

Dijkstra.PriorityQueue.QueueElement is an element of the Queue. It contains an object and his priority.

Implementation of IGraph

Doing Simple Design. The implementation of IGraph is the simplest as possible : an adjacency matrix AM, with AM[start][destination] = weight. If AM[start][destination] = 0, the path does not exist. This implementation is probably not the fastest. Moreover, if the graph has a big number of vertices and a few edges, it wastes a lot of memory. That's why choosing an implementation of the graph depending the number of vertices / edges would be great for performances. Others possible implementations are adjacency list and edge list.

I have chosen to design the graph class as generic as possible. So it is a graph of objects Object ! The objects in the graphs are supposed to be Cloneable or the Finders methods will get some troubles !


Of course, I have written Junit tests (before the implementation as XP practice advises) to test the algorithms. I have also used a MockGraph class to simulate a graph in order to test search algorithms used by PathFinder and Dijkstra.

back to Top

3. Tutorial

We would like to answer these 3 questions :

  • which is the shortest path from A to D ?
  • which is the shortest path from C to E ?
  • which are the number of different paths from A to C with a distance of less than 20 ?

3.1 Write unit tests before you write the code

If you have never heard about Junit and Unit Testing in Extreme Programming, I suggest you to read the short tutorial I have written.

public class LetterGraphFinderTest extends TestCase {

    private LetterGraphFinder finder;

    public LetterGraphFinderTest(String s) {



    protected void setUp() {

        // Set up the graph before each test (this practice avoids side effect)

        LetterGraphBuilder builder = new LetterGraphBuilder(5);

        builder.addPath('A', 'B', 5);

        builder.addPath('B', 'C', 4);

        builder.addPath('C', 'B', 2);

        builder.addPath('C', 'D', 7);

        builder.addPath('E', 'C', 5);

        builder.addPath('D', 'A', 3);

        builder.addPath('D', 'E', 5);

        // Instantiates the finder

        finder = new LetterGraphFinder(builder.getLetterGraph());


    protected void tearDown() {


    public void testFindShortestPath() {

        assertEquals("A-B-C-D", finder.findShortestPath('A', 'D'));

        assertEquals("C-D-E", finder.findShortestPath('C', 'E'));


    public void testFindPathsWithMaximumDistance() {

        ArrayList solutions = (ArrayList) finder.findPathsWithMaximumDistance('A', 'C', 20);

        // Iterate on the solutions, increment counter each time a correct solution is found

        int numberOfCorrectSolutions = 0;

        Iterator iter = solutions.iterator();

        while (iter.hasNext()) {

            String sol =;

            if (sol.equals("A-B-C") || sol.equals("A-B-C-B-C")) {




        // How many solutions found ?

        assertEquals(2, numberOfCorrectSolutions);



3.2 The LetterGraph class :



Title: Graphs API Example




Copyright: Copyright (c) 2002


Company: Unemployed and I think this is not a normal situation :-) * Who said that there is always work for good programmers ? Probably not the English agencies :-)

* @author Jean-Michel Garnier * @version 1.0 */
public class LetterGraph { /** * The implementation of the graph is delegated to the Builder class */ private IGraph graph; /** * * @param graph * @param numberOfLetters */ public LetterGraph(IGraph graph) { this.graph = graph; } /** * Add a new edge to the graph. This method is protected because you are supposed * to use the Builder class to build an object of LetterGraph. Protected modifier does * not allow others packages to access it ! * @param start a String of 1 character * @param end a String of 1 character * @param weight */ protected void addPath(String start, String end, int weight) { // The parameters are not checked because I know that class AdjencyMatrixGraph does it for me ! graph.addEdge(start, end, weight); } /** * This method is protected because you are supposed to access the graph through the FinderClass * @return the graph ! */ protected IGraph getGraph() { return graph; } }

3.3 The Builder class :

public class LetterGraphBuilder {


     * We choose to implement the graph with an adjacency matrix


    private AdjacencyMatrixGraph graph;



     * The object we are going to build


    private LetterGraph letterGraph;



     * @param numberVertices


    public LetterGraphBuilder(int numberVertices) {

        // There is no controls

        graph = new AdjacencyMatrixGraph(numberVertices);

        letterGraph = new LetterGraph(graph);

        // Add the letter vertices "A", "B", etc ... until the number of vertices

        for (int i = 0; i < numberVertices; i++) {

            /* a bit of explanations about this ugly code :

            'A' is a char !

            'A' + i : in java chars can be added to int

            (char) ('A' + i) : converts into a character the result of addition

            To be crystal clear, A + 1 = B ! Very logic isn't it ? 

            Finally, valueOf method converts the char into a String object */

            graph.addVertex( String.valueOf( (char) ('A' + i)) );




     * Add an edge to the graph, wrapper around LetterGraph addPath method

     * @param start vertex

     * @param end vertex

     * @param weight


    public void addPath(char start, char end, int weight) {

        letterGraph.addPath(String.valueOf(start), String.valueOf(end), weight);




     * @return the graph which has been built


    public LetterGraph getLetterGraph() {

        return letterGraph;



3.4 The Finder class :

public class LetterGraphFinder {

    // In fact, class LetterGraphFinder is just a wrapper around PathFinder

    private PathFinder finder;


     * @param letterGraph the graph we are going to use !


    public LetterGraphFinder(LetterGraph letterGraph) {

        finder = new PathFinder(letterGraph.getGraph());



     * @param start letter

     * @param destination letter

     * @return the shortest path in a String format (i.e. A-B-C) or an empty String if no path


    public String findShortestPath(char start, char destination) {

        String s = String.valueOf(start);

        String d = String.valueOf(destination);

        return finder.getShortestPath(s, d).toString();



     * Explore the graph from a start vertex to a destination vertex and find all the paths which have

     * a total distance <= maxDistance. If the destination is reached, its never mind ! continue again and again

     * until the stop condition.

     * @param start letter

     * @param destination letter

     * @param maxDistance the distance is the total of weights of edges between 2 vertex

     * @return


    public List findPathsWithMaximumDistance(char start, char destination, int maxDistance) {

        String s = String.valueOf(start);

        String d = String.valueOf(destination);

        return finder.findPathsWithMaximumDistance(s, d, maxDistance);



back to Top

4. Download


You can download the graphs package here !

Ant instructions

In the build directory, there is a build.xml file. You need to have installed Ant 1.5 to use it ! Here is a short description of the targets:

dist is the default target.

back to Top

5. Links

back to Top






back to Top