Class YenKShortestPath<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:

    public class YenKShortestPath<V,​E>
    extends 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 number of vertices in the graph, $m$ is the number of edges in the graph and $k$ is the number 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. It is possible to provide a PathValidator to filter the resulting path list

    Semen Chudakov
    See Also:
    YenShortestPathIterator, PathValidator
    • Constructor Detail

      • YenKShortestPath

        public YenKShortestPath​(Graph<V,​E> graph)
        Constructs an instance of the algorithm for the given graph.
        graph - graph
      • YenKShortestPath

        public YenKShortestPath​(Graph<V,​E> graph,
                                PathValidator<V,​E> pathValidator)
        Constructs an instance of the algorithm for the given graph and pathValidator.
        graph - graph
        pathValidator - validator for computed paths
    • Method Detail

      • getPaths

        public 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>
        source - the source vertex
        sink - the target vertex
        k - the number of shortest paths to return
        a list of k shortest paths