Package org.jgrapht.alg
Class KShortestPaths<V,E>
java.lang.Object
org.jgrapht.alg.KShortestPaths<V,E>
The algorithm determines the k shortest simple paths in increasing order of
weight. Weights could be negative (but no negative cycle is allowed), paths
could be constrained by a maximum number of edges.
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*m*n) where m is the number of edges and n is the number of vertices.
- Since:
- July 5, 2007
- Author:
- Guillaume Boulmier
-
Constructor Summary
ConstructorsConstructorDescriptionKShortestPaths
(Graph<V, E> graph, V startVertex, int k) Creates an object to compute ranking shortest paths between the start vertex and others vertices.KShortestPaths
(Graph<V, E> graph, V startVertex, int nPaths, int nMaxHops) Creates an object to calculate ranking shortest paths between the start vertex and others vertices. -
Method Summary
-
Constructor Details
-
KShortestPaths
Creates an object to compute ranking shortest paths between the start vertex and others vertices.- Parameters:
graph
-startVertex
-k
- number of paths to be computed.
-
KShortestPaths
Creates an object to calculate ranking shortest paths between the start vertex and others vertices.- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.nPaths
- number of ranking paths between the start vertex and an end vertex.nMaxHops
- maximum number of edges of the calculated paths.- Throws:
NullPointerException
- if the specified graph or startVertex isnull
.IllegalArgumentException
- if nPaths is negative or 0.IllegalArgumentException
- if nMaxHops is negative or 0.
-
-
Method Details
-
getPaths
Returns the k shortest simple paths in increasing order of weight.- Parameters:
endVertex
- target vertex of the calculated paths.- Returns:
- list of paths, or
null
if no path exists between the start vertex and the end vertex.
-