Class KShortestPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    KShortestPathAlgorithm<V,​E>

    public class KShortestPaths<V,​E>
    extends java.lang.Object
    implements KShortestPathAlgorithm<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. Graphs with multiple edges 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
    • Constructor Summary

      Constructors 
      Constructor Description
      KShortestPaths​(Graph<V,​E> graph, int k)
      Constructs an object to compute ranking shortest paths in a graph.
      KShortestPaths​(Graph<V,​E> graph, int k, int nMaxHops)
      Constructs an object to calculate ranking shortest paths in a graph.
      KShortestPaths​(Graph<V,​E> graph, int k, int nMaxHops, PathValidator<V,​E> pathValidator)
      Constructs an object to calculate ranking shortest paths in a graph.
      KShortestPaths​(Graph<V,​E> graph, int k, PathValidator<V,​E> pathValidator)
      Constructs an object to compute ranking shortest paths in a graph.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<GraphPath<V,​E>> getPaths​(V startVertex, 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
    • Field Detail

      • graph

        private Graph<V,​E> graph
        Graph on which shortest paths are searched.
      • nMaxHops

        private int nMaxHops
      • nPaths

        private int nPaths
    • Constructor Detail

      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              int k)
        Constructs an object to compute ranking shortest paths in a graph.
        Parameters:
        graph - graph on which shortest paths are searched
        k - number of paths to be computed
      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              int k,
                              PathValidator<V,​E> pathValidator)
        Constructs an object to compute ranking shortest paths in a graph. A 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 which are that the path is from start to target with no loops.
        Parameters:
        graph - graph on which shortest paths are searched.
        k - number of paths to be computed.
        pathValidator - the path validator to use
        Throws:
        java.lang.IllegalArgumentException - if k is negative or 0.
      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              int k,
                              int nMaxHops)
        Constructs an object to calculate ranking shortest paths in a graph.
        Parameters:
        graph - graph on which shortest paths are searched
        k - number of ranking paths between the start vertex and an end vertex
        nMaxHops - maximum number of edges of the calculated paths
        Throws:
        java.lang.IllegalArgumentException - if k is negative or 0.
        java.lang.IllegalArgumentException - if nMaxHops is negative or 0.
      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              int k,
                              int nMaxHops,
                              PathValidator<V,​E> pathValidator)
        Constructs an object to calculate ranking shortest paths in a graph. A 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 which are that the path is from start to target with no loops.
        Parameters:
        graph - graph on which shortest paths are searched
        k - number of ranking paths between the start vertex and the end vertex
        nMaxHops - maximum number of edges of the calculated paths
        pathValidator - the path validator to use
        Throws:
        java.lang.IllegalArgumentException - if k 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 startVertex,
                                                             V endVertex)
        Returns the k shortest simple paths in increasing order of weight.
        Specified by:
        getPaths in interface KShortestPathAlgorithm<V,​E>
        Parameters:
        startVertex - source vertex of the calculated paths.
        endVertex - target vertex of the calculated paths.
        Returns:
        list of paths between the start vertex and the end vertex
        Throws:
        java.lang.IllegalArgumentException - if the graph does not contain the startVertex or the endVertex
        java.lang.IllegalArgumentException - if the startVertex and the endVertex are the same vertices