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).
- Context description
- Class Diagram
- Tutorial
- Download
- References
- 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
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 :
- shortestPathMap, the result map of the shortest path distances from a start
vertex after running the algorithm
- predecessorsMap, the result map of predecessors of the shortest path from
a start vertex after running the algorithm
- determindedVerticesSet, the set of vertices whose shortest paths from the
source have already been determined
- remainingVerticesQueue, the list of remaining vertices, implemented as a
priority queue
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
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
|
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
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:
- doc - generate javadoc documentation files in the doc directory
- compile - compile sources
- jar - generate a jar file of the package org.rollerjm.graphs
- dist - generate a distribution
- test - compile and execute Junit tests
dist is the default target.
back to Top
back to Top
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