Package org.jgrapht.alg

Class KShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.KShortestPaths<V,E>
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
    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

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

    • 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:
      NullPointerException - if the specified graph or startVertex is null.
      IllegalArgumentException - if nPaths is negative or 0.
      IllegalArgumentException - if nMaxHops is negative or 0.

  • Method Details

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