Graphs and Dijkstra's algorithm | Last update : 10/12/2002 | back to HOME PAGE |
|
Introduction |
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.
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 :
Typical problems which can be solved with graphs :
|
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); } }
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.
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.
3. Tutorial |
![]() |
We would like to answer these 3 questions :
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); } }
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.
5. Links |
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.
|