|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectorg.jgrapht.alg.KShortestPaths<V,E>
public class KShortestPaths<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. Multigraphs 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.
| Constructor Summary | |
|---|---|
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 | |
|---|---|
java.util.List<GraphPath<V,E>> |
getPaths(V endVertex)
Returns the k shortest simple paths in increasing order of weight. |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
|---|
public KShortestPaths(Graph<V,E> graph,
V startVertex,
int k)
graph - startVertex - k - number of paths to be computed.
public KShortestPaths(Graph<V,E> graph,
V startVertex,
int nPaths,
int nMaxHops)
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.
java.lang.NullPointerException - if the specified graph or startVertex is
null.
java.lang.IllegalArgumentException - if nPaths is negative or 0.
java.lang.IllegalArgumentException - if nMaxHops is negative or 0.| Method Detail |
|---|
public java.util.List<GraphPath<V,E>> getPaths(V endVertex)
endVertex - target vertex of the calculated paths.
null if no path exists between the
start vertex and the end vertex.
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||