YenKShortestPath (JGraphT : a free Java graph library)

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 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

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`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
  - 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 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>
    
    Parameters:
    
    source - the source vertex
    
    sink - the target vertex
    
    k - the number of shortest paths to return
    
    Returns:
    
    a list of k shortest paths