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