Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class YenKShortestPath<V,​E>

java.lang.Object
org.jgrapht.alg.shortestpath.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 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

Author:
Semen Chudakov
See Also:
YenShortestPathIterator, PathValidator

  • Constructor Summary

    Constructors 
    Constructor Description
    YenKShortestPath​(Graph<V,​E> graph)
    Constructs an instance of the algorithm for the given graph.
    YenKShortestPath​(Graph<V,​E> graph, PathValidator<V,​E> pathValidator)
    Constructs an instance of the algorithm for the given graph and pathValidator.

  • Method Summary

    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 Details

    • YenKShortestPath

      public YenKShortestPath​(Graph<V,​E> graph)
      Constructs an instance of the algorithm for the given graph.
      Parameters:
      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.
      Parameters:
      graph - graph
      pathValidator - validator for computed paths

  • Method Details

    • 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