Class YenKShortestPath<V,E>
 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>
public class YenKShortestPath<V,E> extends Object implements 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 amount of vertices in the graph, $m$ is the amount of edges in the graph and $k$ is the amount 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 thesink
and forms the resulting list. During the execution the algorithm keeps track of how many candidates with minimum weight exist. If the amount is greater or equal to the amount of path needed to complete the execution, the algorithm retrieves the rest of the path from the candidates heap and adds them to the resulting list. Author:
 Semen Chudakov
 See Also:
YenShortestPathIterator


Constructor Summary
Constructors Constructor Description YenKShortestPath(Graph<V,E> graph)
Constructs an instance of the algorithm for the givengraph
.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description List<GraphPath<V,E>>
getPaths(V source, V sink, int k)
Computesk
shortest loopless paths betweensource
andsink
.



Method Detail

getPaths
public List<GraphPath<V,E>> getPaths(V source, V sink, int k)
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

