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 Object
    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.
    Author:
    Assaf Mizrachi
    • Field Detail

      • workingGraph

        protected Graph<V,​E> workingGraph
        Graph on which shortest paths are searched.
      • pathList

        protected List<List<E>> pathList
      • originalGraph

        protected Graph<V,​E> originalGraph
    • Method Detail

      • transformGraph

        protected void transformGraph​(List<E> previousPath)
        Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding calculateShortestPath(V, V) call.
        Parameters:
        previousPath - the path found at the previous iteration.
      • calculateShortestPath

        protected GraphPath<V,​E> calculateShortestPath​(V startVertex,
                                                             V endVertex)
        Calculates the shortest paths for the current iteration. Path is not final; rather, it is intended to be used in a "post-production" phase (see resolvePaths method).
        Parameters:
        startVertex - the start vertex
        endVertex - the end vertex
        Returns:
        the shortest path between start and end vertices.
      • getPaths

        public List<GraphPath<V,​E>> getPaths​(V startVertex,
                                                   V endVertex,
                                                   int k)
        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.
        k - the number of shortest paths to return
        Returns:
        list of disjoint paths between the start vertex and the end vertex
        Throws:
        IllegalArgumentException - if the graph does not contain the startVertex or the endVertex
        IllegalArgumentException - if the startVertex and the endVertex are the same vertices
        IllegalArgumentException - if the startVertex or the endVertex is null