java.lang.Object
org.jgrapht.alg.shortestpath.YenKShortestPath<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
KShortestPathAlgorithm<V,
E>
Implementation of Yen`s algorithm for finding $k$ shortest loopless paths.
The time complexity of the algorithm is $O(kn(m + n log n))$, where $n$ is the number of vertices in the graph, $m$ is the number of edges in the graph and $k$ is the number of paths needed.
The algorithm is originally described in: Q. V. Martins, Ernesto and M. B. Pascoal, Marta. (2003). A new implementation of Yenâ€™s ranking loopless paths algorithm. Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 1. 121133. 10.1007/s1028800200102.
The implementation iterates over the existing loopless path between the source
and the
sink
and forms the resulting list. It is possible to provide a PathValidator
to
filter the resulting path list
 Author:
 Semen Chudakov
 See Also:

Constructor Summary
ConstructorDescriptionYenKShortestPath
(Graph<V, E> graph) Constructs an instance of the algorithm for the givengraph
.YenKShortestPath
(Graph<V, E> graph, PathValidator<V, E> pathValidator) Constructs an instance of the algorithm for the givengraph
andpathValidator
. 
Method Summary

Constructor Details

YenKShortestPath
Constructs an instance of the algorithm for the givengraph
. Parameters:
graph
 graph

YenKShortestPath
Constructs an instance of the algorithm for the givengraph
andpathValidator
. Parameters:
graph
 graphpathValidator
 validator for computed paths


Method Details

getPaths
Computesk
shortest loopless paths betweensource
andsink
. If the overall number of such paths is denoted by $n$, the method returns $m = min\{k, n\}$ such paths. The paths are produced in sorted order by weights. Specified by:
getPaths
in interfaceKShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertexsink
 the target vertexk
 the number of shortest paths to return Returns:
 a list of k shortest paths
