V
 the graph vertex typeE
 the graph edge typepublic class KShortestSimplePaths<V,E> extends Object implements KShortestPathAlgorithm<V,E>
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 and 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.

Modifier and Type  Method and 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.

public KShortestSimplePaths(Graph<V,E> graph)
graph
 graph on which shortest paths are searchedpublic KShortestSimplePaths(Graph<V,E> graph, PathValidator<V,E> pathValidator)
graph
 graph on which shortest paths are searched.pathValidator
 the path validator to usepublic KShortestSimplePaths(Graph<V,E> graph, int nMaxHops)
graph
 graph on which shortest paths are searchednMaxHops
 maximum number of edges of the calculated pathsIllegalArgumentException
 if nMaxHops is negative or 0.public KShortestSimplePaths(Graph<V,E> graph, int nMaxHops, PathValidator<V,E> pathValidator)
graph
 graph on which shortest paths are searchednMaxHops
 maximum number of edges of the calculated pathspathValidator
 the path validator to useIllegalArgumentException
 if nMaxHops is negative or 0.public List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
getPaths
in interface KShortestPathAlgorithm<V,E>
startVertex
 source vertex of the calculated paths.endVertex
 target vertex of the calculated paths.k
 the number of shortest paths to returnIllegalArgumentException
 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 zeroCopyright © 2019. All rights reserved.