Package org.jgrapht.alg
Class KShortestPaths<V,E>
- java.lang.Object
-
- org.jgrapht.alg.KShortestPaths<V,E>
-
public class KShortestPaths<V,E> extends java.lang.Object
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
Constructors Constructor Description KShortestPaths(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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.List<GraphPath<V,E>>
getPaths(V endVertex)
Returns the k shortest simple paths in increasing order of weight.
-
-
-
Constructor Detail
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, V startVertex, int k)
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
public 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.- 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:
java.lang.NullPointerException
- if the specified graph or startVertex isnull
.java.lang.IllegalArgumentException
- if nPaths is negative or 0.java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
-