V
 the graph vertex typeE
 the graph edge typepublic class KShortestPaths<V,E> extends Object
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*n*(m^2)) where m is the number of edges and n is the number of vertices.
Constructor and Description 

KShortestPaths(Graph<V,E> graph,
V startVertex,
int k)
Creates an object to compute ranking shortest paths between the start vertex and others
vertices.

KShortestPaths(Graph<V,E> graph,
V startVertex,
int nPaths,
int nMaxHops)
Creates an object to calculate ranking shortest paths between the start vertex and others
vertices.

KShortestPaths(Graph<V,E> graph,
V startVertex,
int nPaths,
int nMaxHops,
PathValidator<V,E> pathValidator)
Creates an object to calculate ranking shortest paths between the start vertex and others
vertices.

KShortestPaths(Graph<V,E> graph,
V startVertex,
int k,
PathValidator<V,E> pathValidator)
Creates an object to compute ranking shortest paths between the start vertex and others
vertices.

Modifier and Type  Method and Description 

List<GraphPath<V,E>> 
getPaths(V endVertex)
Returns the k shortest simple paths in increasing order of weight.

public KShortestPaths(Graph<V,E> graph, V startVertex, int k)
graph
 graph on which shortest paths are searched.startVertex
 start vertex of the calculated paths.k
 number of paths to be computed.public KShortestPaths(Graph<V,E> graph, V startVertex, int k, PathValidator<V,E> pathValidator)
graph
 graph on which shortest paths are searched.startVertex
 start vertex of the calculated paths.k
 number of paths to be computed.pathValidator
 the path validator to usepublic KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops)
graph
 graph on which shortest paths are searched.startVertex
 start vertex of the calculated paths.nPaths
 number of ranking paths between the start vertex and an end vertex.nMaxHops
 maximum number of edges of the calculated paths.NullPointerException
 if the specified graph or startVertex is null
.IllegalArgumentException
 if nPaths is negative or 0.IllegalArgumentException
 if nMaxHops is negative or 0.public KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops, PathValidator<V,E> pathValidator)
graph
 graph on which shortest paths are searched.startVertex
 start vertex of the calculated paths.nPaths
 number of ranking paths between the start vertex and an end vertex.nMaxHops
 maximum number of edges of the calculated paths.pathValidator
 the path validator to useNullPointerException
 if the specified graph or startVertex is null
.IllegalArgumentException
 if nPaths is negative or 0.IllegalArgumentException
 if nMaxHops is negative or 0.Copyright © 2016. All rights reserved.