com.samskivert.util

Class ShortestPath

java.lang.Object

com.samskivert.util.ShortestPath

public class ShortestPath
extends Object

Implements Dijkstra's algorithm for finding the shortest path between two nodes in a weighted graph. The code assumes that the caller represents their nodes and edges as objects which can be compared and hashed (via Object.equals(java.lang.Object) and Object.hashCode()) other necessary information is obtained through a special interface ShortestPath.Graph implemented by the caller to enumerate edges and compute weights.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	ShortestPath.Graph<T,V> A caller must implement this interface to provide the information needed to define the graph and compute the shortest path.

Constructor Summary

Constructors

Constructor and Description
ShortestPath()

Method Summary

Modifier and Type	Method and Description
static <T,V> List<V>	compute(ShortestPath.Graph<T,V> graph, T start, T end) Computes the shortest path between the specified starting and ending nodes using Dijkstra's algorithm.

Methods inherited from class java.lang.Object

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

Constructor Detail

ShortestPath

public ShortestPath()

Method Detail

compute

public static <T,V> List<V> compute(ShortestPath.Graph<T,V> graph,
                                    T start,
                                    T end)

Computes the shortest path between the specified starting and ending nodes using Dijkstra's algorithm. This implementation assumes that the graph is properly formed and may behave strangely or throw an exception if provided with an invalid graph.

Returns:

a list of the edges that must be followed to traverse from the starting node to the ending node. This list may be empty if the graph is improperly formed.