gov.nasa.arc.brahms.vm.rt
Class ShortestPathAlgorithm

java.lang.Object
  gov.nasa.arc.brahms.vm.rt.ShortestPathAlgorithm

public class ShortestPathAlgorithm
extends java.lang.Object

The ShortestPathAlgorithm provides an implementation of Dijkstra's shortest path algorithm. It is used to determine the shortest distance and path between two areas in the geography of a Brahms model.

Version:

$Revision: 1.2 $ $Date: 2008/02/28 19:46:51 $ $Author: rvhoof $

Author:

Ron van Hoof

Nested Class Summary

class

ShortestPathAlgorithm.ShortestPath The ShortestPath specifies the start and end location of the 'traveled' path, the distance of the path and the path taken from the start location to the end location.

Field Summary

static long

INFINITE The infinite value to indicate the non-existence of a path between nodes

Constructor Summary

ShortestPathAlgorithm()
Constructor, creates a new instance of the ShortestPathAlgorithm.

Method Summary

ShortestPathAlgorithm.ShortestPath	getShortestPath(VMAreaCtx start, VMAreaCtx end) Determines the shortest path from the specified start location to the specified end location.
static ShortestPathAlgorithm	getShortestPathAlgorithm() Returns Dijkstra's shortest path algorithm used to determine the shortest distance and path from one area to another.
void	init(Model model) Initializes the shortest path algorithm by placing all areas in the geography in a list and creating a distance matrix used by the shortest path algorithm.
void	reset() Resets the shortest path algorithm removing all areas from the list and emptying the distance matrix.

Methods inherited from class java.lang.Object

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

Field Detail

INFINITE

public static final long INFINITE

The infinite value to indicate the non-existence of a path between nodes

See Also:

Constant Field Values

Constructor Detail

ShortestPathAlgorithm

public ShortestPathAlgorithm()

Constructor, creates a new instance of the ShortestPathAlgorithm.

Method Detail

getShortestPathAlgorithm

public static ShortestPathAlgorithm getShortestPathAlgorithm()

Returns Dijkstra's shortest path algorithm used to determine the shortest distance and path from one area to another.

Returns:

ShortestPathAlgorithm the shortest path algorithm

init

public void init(Model model)

Initializes the shortest path algorithm by placing all areas in the geography in a list and creating a distance matrix used by the shortest path algorithm.

Parameters:

model - the Model containing the areas and paths that are part of the geography of the model.

getShortestPath

public final ShortestPathAlgorithm.ShortestPath getShortestPath(VMAreaCtx start,
                                                                VMAreaCtx end)

Determines the shortest path from the specified start location to the specified end location. It returns null if no path exists between the two locations.

Parameters:

start - the start location

end - the end location

Returns:

ShortestPathAlgorithm.ShortestPath the shortest path and distance if a path was found, null if no path was found

reset

public void reset()

Resets the shortest path algorithm removing all areas from the list and emptying the distance matrix.