Package org.jgrapht.alg.shortestpath
Class KShortestSimplePaths<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.KShortestSimplePaths<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
KShortestPathAlgorithm<V,E>
public class KShortestSimplePaths<V,E> extends java.lang.Object implements KShortestPathAlgorithm<V,E>
The algorithm determines the k shortest simple paths in increasing order of weight. Weights can be negative (but no negative cycle is allowed), and paths can be constrained by a maximum number of edges. Graphs with multiple (parallel) edges are allowed.The algorithm is a variant of the Bellman-Ford algorithm but instead of only storing the best path it stores the "k" best paths at each pass, yielding a complexity of $O(k \cdot n \cdot (m^2))$ where $m$ is the number of edges and $n$ is the number of vertices.
-
-
Constructor Summary
Constructors Constructor Description KShortestSimplePaths(Graph<V,E> graph)
Constructs an object to compute ranking shortest paths in a graph.KShortestSimplePaths(Graph<V,E> graph, int nMaxHops)
Constructs an object to calculate ranking shortest paths in a graph.KShortestSimplePaths(Graph<V,E> graph, int nMaxHops, PathValidator<V,E> pathValidator)
Constructs an object to calculate ranking shortest paths in a graph.KShortestSimplePaths(Graph<V,E> graph, PathValidator<V,E> pathValidator)
Constructs an object to compute ranking shortest paths in a graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.List<GraphPath<V,E>>
getPaths(V startVertex, V endVertex, int k)
Returns a list of the $k$ shortest simple paths in increasing order of weight.
-
-
-
Constructor Detail
-
KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph)
Constructs an object to compute ranking shortest paths in a graph.- Parameters:
graph
- graph on which shortest paths are searched
-
KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph, PathValidator<V,E> pathValidator)
Constructs an object to compute ranking shortest paths in a graph. A non-null path validator may be used to accept/deny paths according to some external logic. These validations will be used in addition to the basic path validations which are that the path is from start to target with no loops.- Parameters:
graph
- graph on which shortest paths are searched.pathValidator
- the path validator to use
-
KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph, int nMaxHops)
Constructs an object to calculate ranking shortest paths in a graph.- Parameters:
graph
- graph on which shortest paths are searchednMaxHops
- maximum number of edges of the calculated paths- Throws:
java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
KShortestSimplePaths
public KShortestSimplePaths(Graph<V,E> graph, int nMaxHops, PathValidator<V,E> pathValidator)
Constructs an object to calculate ranking shortest paths in a graph. A non-null path validator may be used to accept/deny paths according to some external logic. These validations will be used in addition to the basic path validations which are that the path is from start to target with no loops.- Parameters:
graph
- graph on which shortest paths are searchednMaxHops
- maximum number of edges of the calculated pathspathValidator
- the path validator to use- Throws:
java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
-
Method Detail
-
getPaths
public java.util.List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
Returns a list of the $k$ shortest simple paths in increasing order of weight.- Specified by:
getPaths
in interfaceKShortestPathAlgorithm<V,E>
- Parameters:
startVertex
- source vertex of the calculated paths.endVertex
- target vertex of the calculated paths.k
- the number of shortest paths to return- Returns:
- an iterator of paths between the start vertex and the end vertex
- Throws:
java.lang.IllegalArgumentException
- if the graph does not contain the startVertex or the endVertexjava.lang.IllegalArgumentException
- if the startVertex and the endVertex are the same verticesjava.lang.IllegalArgumentException
- if k is negative or zero
-
-