Package org.jgrapht.alg.shortestpath
Class KShortestSimplePaths<V,E>
 java.lang.Object

 org.jgrapht.alg.shortestpath.KShortestSimplePaths<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
KShortestPathAlgorithm<V,E>
public class KShortestSimplePaths<V,E> extends Object implements KShortestPathAlgorithm<V,E>
The algorithm determines the k shortest simple paths in increasing order of weight. Weights can be negative (but no negative cycle is allowed), and paths can be constrained by a maximum number of edges. Graphs with multiple (parallel) edges are allowed.The algorithm is a variant of the BellmanFord algorithm but instead of only storing the best path it stores the "k" best paths at each pass, yielding a complexity of $O(k \cdot n \cdot (m^2))$ where $m$ is the number of edges and $n$ is the number of vertices.


Constructor Summary
Constructors Constructor Description KShortestSimplePaths(Graph<V,E> graph)
Constructs an object to compute ranking shortest paths in a graph.KShortestSimplePaths(Graph<V,E> graph, int nMaxHops)
Constructs an object to calculate ranking shortest paths in a graph.KShortestSimplePaths(Graph<V,E> graph, int nMaxHops, PathValidator<V,E> pathValidator)
Constructs an object to calculate ranking shortest paths in a graph.KShortestSimplePaths(Graph<V,E> graph, PathValidator<V,E> pathValidator)
Constructs an object to compute ranking shortest paths in a graph.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description List<GraphPath<V,E>>
getPaths(V startVertex, V endVertex, int k)
Returns a list of the $k$ shortest simple paths in increasing order of weight.



Constructor Detail

KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph)
Constructs an object to compute ranking shortest paths in a graph. Parameters:
graph
 graph on which shortest paths are searched

KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph, PathValidator<V,E> pathValidator)
Constructs an object to compute ranking shortest paths in a graph. A nonnull path validator may be used to accept/deny paths according to some external logic. These validations will be used in addition to the basic path validations which are that the path is from start to target with no loops. Parameters:
graph
 graph on which shortest paths are searched.pathValidator
 the path validator to use

KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph, int nMaxHops)
Constructs an object to calculate ranking shortest paths in a graph. Parameters:
graph
 graph on which shortest paths are searchednMaxHops
 maximum number of edges of the calculated paths Throws:
IllegalArgumentException
 if nMaxHops is negative or 0.

KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph, int nMaxHops, PathValidator<V,E> pathValidator)
Constructs an object to calculate ranking shortest paths in a graph. A nonnull path validator may be used to accept/deny paths according to some external logic. These validations will be used in addition to the basic path validations which are that the path is from start to target with no loops. Parameters:
graph
 graph on which shortest paths are searchednMaxHops
 maximum number of edges of the calculated pathspathValidator
 the path validator to use Throws:
IllegalArgumentException
 if nMaxHops is negative or 0.


Method Detail

getPaths
public List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
Returns a list of the $k$ shortest simple paths in increasing order of weight. Specified by:
getPaths
in interfaceKShortestPathAlgorithm<V,E>
 Parameters:
startVertex
 source vertex of the calculated paths.endVertex
 target vertex of the calculated paths.k
 the number of shortest paths to return Returns:
 an iterator of paths between the start vertex and the end vertex
 Throws:
IllegalArgumentException
 if the graph does not contain the startVertex or the endVertexIllegalArgumentException
 if the startVertex and the endVertex are the same verticesIllegalArgumentException
 if k is negative or zero

