Package org.jgrapht.alg.shortestpath

Class EppsteinKShortestPath<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.EppsteinKShortestPath<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

KShortestPathAlgorithm<V,E>

public class EppsteinKShortestPath<V,E>
extends Object
implements 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), 652-673. 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:

EppsteinShortestPathIterator

Constructor Summary

Constructors

Constructor	Description
EppsteinKShortestPath(Graph<V,E> graph)	Constructs the algorithm instance for the given graph.

Method Summary

Modifier and Type	Method	Description
List<GraphPath<V,E>>	getPaths(V source, V sink, int k)	Computes k shortest paths between source and sink.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EppsteinKShortestPath

public EppsteinKShortestPath(Graph<V,E> graph)

Constructs the algorithm instance for the given graph.

Parameters:

graph - graph

Method Detail

getPaths

public List<GraphPath<V,E>> getPaths(V source,
                                           V sink,
                                           int k)

Computes k shortest paths between source and sink. 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 interface KShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

sink - the target vertex

k - the number of shortest paths to return

Returns:

a list of k shortest paths