org.rblasch.convert.dijkstra
Class ShortestPathEngine

java.lang.Object
  org.rblasch.convert.dijkstra.ShortestPathEngine

public class ShortestPathEngine

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 vertex to every other vertex, and the shortest path from the start vertex to every other.

Upon calling execute(Vertex, Vertex), the results of the algorithm are made available by calling getPredecessor(Vertex) and getShortestDistance(Vertex).

To get the shortest path between the vertex destination and the source vertex after running the algorithm, one would do:

 List l = new ArrayList();
 

 for (Object vertex = destination; vertex != null; vertex = engine.getPredecessor(vertex))
 {
     l.add(vertex);
 }
 

 Collections.reverse(l);
 

 return l;
 

Version:

$Id: DijkstraEngine.java,v 1.4 2003/03/03 01:26:22 renaud Exp $

Author:

Renaud Waldura <renaud+tw@waldura.com>

See Also:

execute(Vertex, Vertex)

Field Summary

static int

INFINITE_DISTANCE Infinity value for distances.

Constructor Summary

ShortestPathEngine(WeightedDirectedGraph map)
Constructor.

Method Summary

void	execute(Vertex start, Vertex destination) Run Dijkstra's shortest path algorithm on the map.
int	getMinWeight(Vertex start, Vertex end) Get the value of a segment.
Vertex	getPredecessor(Vertex vertex)
int	getShortestDistance(Vertex vertex)
Path	getShortestPath(Vertex start, Vertex end)

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

Constructor Detail

ShortestPathEngine

public ShortestPathEngine(WeightedDirectedGraph map)

Constructor.

Method Detail

execute

public void execute(Vertex start,
                    Vertex destination)

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

Parameters:

start - the starting vertex

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

getShortestPath

public Path getShortestPath(Vertex start,
                            Vertex end)

getMinWeight

public int getMinWeight(Vertex start,
                        Vertex end)

Get the value of a segment.

getShortestDistance

public int getShortestDistance(Vertex vertex)

Returns:

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

getPredecessor

public Vertex getPredecessor(Vertex vertex)

Returns:

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