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.