org.jgrapht.alg

Class KShortestPaths<V,E>

java.lang.Object

org.jgrapht.alg.KShortestPaths<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class KShortestPaths<V,E>
extends Object

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.

Since:

July 5, 2007

Author:

Guillaume Boulmier

Constructor Summary

Constructors

Constructor and 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.
KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops, PathValidator<V,E> pathValidator) Creates an object to calculate ranking shortest paths between the start vertex and others vertices.
KShortestPaths(Graph<V,E> graph, V startVertex, int k, PathValidator<V,E> pathValidator) Creates an object to compute ranking shortest paths between the start vertex and others vertices.

Method Summary

Modifier and Type	Method and Description
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

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 - graph on which shortest paths are searched.

startVertex - start vertex of the calculated paths.

k - number of paths to be computed.

KShortestPaths

public KShortestPaths(Graph<V,E> graph,
                      V startVertex,
                      int k,
                      PathValidator<V,E> pathValidator)

Creates an object to compute ranking shortest paths between the start vertex and others vertices. Providing 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 - that the path is from start to target with no loops.

Parameters:

graph - graph on which shortest paths are searched.

startVertex - start vertex of the calculated paths.

k - number of paths to be computed.

pathValidator - the path validator to use

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:

NullPointerException - if the specified graph or startVertex is null.

IllegalArgumentException - if nPaths is negative or 0.

IllegalArgumentException - if nMaxHops is negative or 0.

KShortestPaths

public KShortestPaths(Graph<V,E> graph,
                      V startVertex,
                      int nPaths,
                      int nMaxHops,
                      PathValidator<V,E> pathValidator)

Creates an object to calculate ranking shortest paths between the start vertex and others vertices. Providing 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 - that the path is from start to target with no loops.

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.

pathValidator - the path validator to use

Throws:

NullPointerException - if the specified graph or startVertex is null.

IllegalArgumentException - if nPaths is negative or 0.

IllegalArgumentException - if nMaxHops is negative or 0.

Method Detail

getPaths

public List<GraphPath<V,E>> getPaths(V endVertex)

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.