V
- the graph vertex typeE
- the graph edge typepublic class YenKShortestPath<V,E> extends Object implements KShortestPathAlgorithm<V,E>
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. 121-133. 10.1007/s10288-002-0010-2.
The implementation iterates over the existing loopless path between the source
and the
sink
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.
YenShortestPathIterator
Constructor and Description |
---|
YenKShortestPath(Graph<V,E> graph)
Constructs an instance of the algorithm for the given
graph . |
Modifier and Type | Method and Description |
---|---|
List<GraphPath<V,E>> |
getPaths(V source,
V sink,
int k)
Computes
k shortest loopless paths between source and sink . |
public List<GraphPath<V,E>> getPaths(V source, V sink, int k)
k
shortest loopless paths between source
and sink
. 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.getPaths
in interface KShortestPathAlgorithm<V,E>
source
- the source vertexsink
- the target vertexk
- the number of shortest paths to returnCopyright © 2019. All rights reserved.