Class BhandariKDisjointShortestPaths<V,​E>

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

    public class BhandariKDisjointShortestPaths<V,​E>
    extends BaseKDisjointShortestPathsAlgorithm<V,​E>
    An implementation of Bhandari algorithm for finding $K$ edge-disjoint shortest paths. The algorithm determines the $k$ edge-disjoint shortest simple paths in increasing order of weight. Weights can be negative (but no negative cycle is allowed). Only directed simple graphs are allowed.

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

    • Bhandari, Ramesh 1999. Survivable networks: algorithms for diverse routing. 477. Springer. p. 46. ISBN 0-7923-8381-8.
    • Iqbal, F. and Kuipers, F. A. 2015. Disjoint Paths in Networks . Wiley Encyclopedia of Electrical and Electronics Engineering. 1–11.
    • Constructor Detail

      • BhandariKDisjointShortestPaths

        public BhandariKDisjointShortestPaths​(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.