Package org.jgrapht.alg.shortestpath

Class 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 java.lang.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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.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 java.util.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