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