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

Introduction
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

Definition

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

        shortestPathMap.clear();

        predecessorsMap.clear();

        determinedVerticesSet.clear();

        remainingVerticesQueue.clear();



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

                break;

            }



            //  Add the closest vertex to the determined Vertices set

			determinedVerticesSet.add(closest);



            // Relaxation, see explanations below

            relax(closest);

        }

    }





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

     * if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v.

     * @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 = adjacentVertices.next();



            // 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 !

Tests

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

        super(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 = iter.next().toString();

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

                numberOfCorrectSolutions++;

            }

        }

        // How many solutions found ?

        assertEquals(2, numberOfCorrectSolutions);

    }



}



3.2 The LetterGraph class :

/**

 * 

Title: Graphs API Example

*

Description:

*

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

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

Credits

Author

I am an European software engineer who lives and works in London. For any comments / suggestions : send an e-mail to g a r n i e r j m @ y a h o o.f r (remove the spaces to get my e-mail, I have done that bc the sobig virus has filled my mailbox!)

Copyrights

The source is free to use and is available under the GNU GENERAL PUBLIC LICENSE.

back to Top