Class YenKShortestPath<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    KShortestPathAlgorithm<V,​E>

    public class YenKShortestPath<V,​E>
    extends java.lang.Object
    implements KShortestPathAlgorithm<V,​E>
    Implementation of Yen`s algorithm for finding $k$ shortest loopless paths.

    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.

    Author:
    Semen Chudakov
    See Also:
    YenShortestPathIterator
    • Constructor Summary

      Constructors 
      Constructor Description
      YenKShortestPath​(Graph<V,​E> graph)
      Constructs an instance of the algorithm 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 loopless 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

      • YenKShortestPath

        public YenKShortestPath​(Graph<V,​E> graph)
        Constructs an instance of the algorithm 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 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.
        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