Class SuurballeKDisjointShortestPaths<V,​E>

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

    public class SuurballeKDisjointShortestPaths<V,​E>
    extends BaseKDisjointShortestPathsAlgorithm<V,​E>
    An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths. The algorithm determines the k disjoint shortest simple paths in increasing order of weight. Only directed simple graphs are allowed.

    The algorithm is running k sequential Dijkstra iterations to find the shortest path at each step. Hence, yielding a complexity of k*O(Dijkstra).

    For further reference see Wikipedia page

    • Suurballe, J. W.; Tarjan, R. E. (1984), A quick method for finding shortest pairs of disjoint paths.
    • Constructor Detail

      • SuurballeKDisjointShortestPaths

        public SuurballeKDisjointShortestPaths​(Graph<V,​E> graph)
        Creates a new instance of the algorithm.
        Parameters:
        graph - graph on which shortest paths are searched.
        Throws:
        java.lang.IllegalArgumentException - if the graph is null.
        java.lang.IllegalArgumentException - if the graph is undirected.
        java.lang.IllegalArgumentException - if the graph is not simple.