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

java.lang.Object
  extended by 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 can be negative (but no negative cycle is allowed), and paths can be constrained by a maximum number of edges. This algorithm should not be used with multigraphs.

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
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

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 is null.
java.lang.IllegalArgumentException - if nPaths 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 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.