java.lang.Object
org.jgrapht.alg.shortestpath.EppsteinKShortestPath<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
KShortestPathAlgorithm<V,
E>
Implementation of the Eppstein`s algorithm for finding $k$ shortest path between two vertices in
a graph.
The algorithm is originally described in: David Eppstein. 1999. Finding the k Shortest Paths. SIAM J. Comput. 28, 2 (February 1999), 652673. DOI=http://dx.doi.org/10.1137/S0097539795290477.
The main advantage ot this algorithm is that it achieves the complexity of $O(m + n\log n + k\log k)$ while guaranteeing that the paths are produced in sorted order by weight, where $m$ is the number of edges in the graph, $n$ is the number of vertices in the graph and $k$ is the number of paths needed.
This implementation can only be used for directed simple graphs.
 Author:
 Semen Chudakov
 See Also:

Constructor Summary
ConstructorDescriptionEppsteinKShortestPath
(Graph<V, E> graph) Constructs the algorithm instance for the givengraph
. 
Method Summary

Constructor Details

EppsteinKShortestPath
Constructs the algorithm instance for the givengraph
. Parameters:
graph
 graph


Method Details

getPaths
Computesk
shortest paths betweensource
andsink
. If the number of 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
