Package org.jgrapht.alg.shortestpath
Class KShortestPaths<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.KShortestPaths<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
KShortestPathAlgorithm<V,E>
public class KShortestPaths<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 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*n*(m^2)) where m is the number of edges and n is the number of vertices.
- Since:
- July 5, 2007
-
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
Graph on which shortest paths are searched.private int
nMaxHops
private int
nPaths
private PathValidator<V,E>
pathValidator
-
Constructor Summary
Constructors Constructor Description KShortestPaths(Graph<V,E> graph, int k)
Constructs an object to compute ranking shortest paths in a graph.KShortestPaths(Graph<V,E> graph, int k, int nMaxHops)
Constructs an object to calculate ranking shortest paths in a graph.KShortestPaths(Graph<V,E> graph, int k, int nMaxHops, PathValidator<V,E> pathValidator)
Constructs an object to calculate ranking shortest paths in a graph.KShortestPaths(Graph<V,E> graph, int k, 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)
Returns the k shortest simple paths in increasing order of weight.
-
-
-
Constructor Detail
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, int k)
Constructs an object to compute ranking shortest paths in a graph.- Parameters:
graph
- graph on which shortest paths are searchedk
- number of paths to be computed
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, int k, 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.k
- number of paths to be computed.pathValidator
- the path validator to use- Throws:
java.lang.IllegalArgumentException
- if k is negative or 0.
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, int k, int nMaxHops)
Constructs an object to calculate ranking shortest paths in a graph.- Parameters:
graph
- graph on which shortest paths are searchedk
- number of ranking paths between the start vertex and an end vertexnMaxHops
- maximum number of edges of the calculated paths- Throws:
java.lang.IllegalArgumentException
- if k is negative or 0.java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, int k, 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 searchedk
- number of ranking paths between the start vertex and the end vertexnMaxHops
- maximum number of edges of the calculated pathspathValidator
- the path validator to use- Throws:
java.lang.IllegalArgumentException
- if k is negative or 0.java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
-
Method Detail
-
getPaths
public java.util.List<GraphPath<V,E>> getPaths(V startVertex, V endVertex)
Returns 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.- Returns:
- list 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 vertices
-
-