com.waldura.tw
Class DijkstraEngine

java.lang.Object
  com.waldura.tw.DijkstraEngine

public class DijkstraEngine
extends java.lang.Object

An implementation of Dijkstra's shortest path algorithm. It computes the shortest path (in distance) to all cities in the map. The output of the algorithm is the shortest distance from the start city to every other city, and the shortest path from the start city to every other.

Upon calling execute(City, City), the results of the algorithm are made available by calling getPredecessor(City) and getShortestDistance(City). To get the shortest path between the city destination and the source city after running the algorithm, one would do:

 ArrayList<City> l = new ArrayList<City>();

 for (City city = destination; city != null; city = engine.getPredecessor(city))
 {
     l.add(city);
 }

 Collections.reverse(l);

 return l;
 

Version:

$Id: DijkstraEngine.java 2379 2007-08-23 19:06:29Z renaud $

Author:

Renaud Waldura <renaud+tw@waldura.com>

See Also:

execute(City, City)

Field Summary

static int	INFINITE_DISTANCE Infinity value for distances.
private static int	INITIAL_CAPACITY Some value to initialize the priority queue with.
private RoutesMap	map The graph.
private java.util.Map<City,City>	predecessors Predecessors list: maps a city to its predecessor in the spanning tree of shortest paths.
private java.util.Set<City>	settledNodes The set of cities for which the shortest distance to the source has been found.
private java.util.Comparator<City>	shortestDistanceComparator This comparator orders cities according to their shortest distances, in ascending fashion.
private java.util.Map<City,java.lang.Integer>	shortestDistances The currently known shortest distance for all cities.
private java.util.PriorityQueue<City>	unsettledNodes The working set of cities, kept ordered by shortest distance.

Constructor Summary

DijkstraEngine(RoutesMap map)
Constructor.

Method Summary

void	execute(City start, City destination) Run Dijkstra's shortest path algorithm on the map.
City	getPredecessor(City city)
int	getShortestDistance(City city)
private void	init(City start) Initialize all data structures used by the algorithm.
private boolean	isSettled(City v) Test a node.
private void	relaxNeighbors(City u) Compute new shortest distance for neighboring nodes and update if a shorter distance is found.
private void	setPredecessor(City a, City b)
private void	setShortestDistance(City city, int distance) Set the new shortest distance for the given node, and re-balance the queue according to new shortest distances.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INFINITE_DISTANCE

public static final int INFINITE_DISTANCE

Infinity value for distances.

See Also:

Constant Field Values

INITIAL_CAPACITY

private static final int INITIAL_CAPACITY

Some value to initialize the priority queue with.

See Also:

Constant Field Values

shortestDistanceComparator

private final java.util.Comparator<City> shortestDistanceComparator

This comparator orders cities according to their shortest distances, in ascending fashion. If two cities have the same shortest distance, we compare the cities themselves.

map

private final RoutesMap map

The graph.

unsettledNodes

private final java.util.PriorityQueue<City> unsettledNodes

The working set of cities, kept ordered by shortest distance.

settledNodes

private final java.util.Set<City> settledNodes

The set of cities for which the shortest distance to the source has been found.

shortestDistances

private final java.util.Map<City,java.lang.Integer> shortestDistances

The currently known shortest distance for all cities.

predecessors

private final java.util.Map<City,City> predecessors

Predecessors list: maps a city to its predecessor in the spanning tree of shortest paths.

Constructor Detail

DijkstraEngine

public DijkstraEngine(RoutesMap map)

Constructor.

Method Detail

init

private void init(City start)

Initialize all data structures used by the algorithm.

Parameters:

start - the source node

execute

public void execute(City start,
                    City destination)

Run Dijkstra's shortest path algorithm on the map. The results of the algorithm are available through getPredecessor(City) and getShortestDistance(City) upon completion of this method.

Parameters:

start - the starting city

destination - the destination city. If this argument is null, the algorithm is run on the entire graph, instead of being stopped as soon as the destination is reached.

relaxNeighbors

private void relaxNeighbors(City u)

Compute new shortest distance for neighboring nodes and update if a shorter distance is found.

Parameters:

u - the node

isSettled

private boolean isSettled(City v)

Test a node.

Parameters:

v - the node to consider

Returns:

whether the node is settled, ie. its shortest distance has been found.

getShortestDistance

public int getShortestDistance(City city)

Returns:

the shortest distance from the source to the given city, or INFINITE_DISTANCE if there is no route to the destination.

setShortestDistance

private void setShortestDistance(City city,
                                 int distance)

Set the new shortest distance for the given node, and re-balance the queue according to new shortest distances.

Parameters:

city - the node to set

distance - new shortest distance value

getPredecessor

public City getPredecessor(City city)

Returns:

the city leading to the given city on the shortest path, or null if there is no route to the destination.

setPredecessor

private void setPredecessor(City a,
                            City b)