Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class BhandariKDisjointShortestPaths<V,E>
java.lang.Object
org.jgrapht.alg.shortestpath.BhandariKDisjointShortestPaths<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
KShortestPathAlgorithm<V,
E>
An implementation of Bhandari algorithm for finding $K$ edgedisjoint shortest paths.
The algorithm determines the $k$ edgedisjoint 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 BellmanFord iterations to find the shortest path at each step. Hence, yielding a complexity of $k$*O(BellmanFord).
 Bhandari, Ramesh 1999. Survivable networks: algorithms for diverse routing. 477. Springer. p. 46. ISBN 0792383818.
 Iqbal, F. and Kuipers, F. A. 2015. Disjoint Paths in Networks . Wiley Encyclopedia of Electrical and Electronics Engineering. 1–11.
 Author:
 Assaf Mizrachi

Field Summary

Constructor Summary
ConstructorDescriptionBhandariKDisjointShortestPaths
(Graph<V, E> graph) Creates a new instance of the algorithm. 
Method Summary
Modifier and TypeMethodDescriptioncalculateShortestPath
(V startVertex, V endVertex) Calculates the shortest paths for the current iteration.Returns the $k$ shortest simple paths in increasing order of weight.protected void
transformGraph
(List<E> previousPath) Prepares the working graph for next iteration.

Field Details

workingGraph
Graph on which shortest paths are searched. 
pathList

originalGraph


Constructor Details

BhandariKDisjointShortestPaths
Creates a new instance of the algorithm. Parameters:
graph
 graph on which shortest paths are searched. Throws:
IllegalArgumentException
 if the graph is null.IllegalArgumentException
 if the graph is undirected.IllegalArgumentException
 if the graph is not simple.


Method Details

transformGraph
Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a precedingcalculateShortestPath(V, V)
call. Parameters:
previousPath
 the path found at the previous iteration.

calculateShortestPath
Calculates the shortest paths for the current iteration. Path is not final; rather, it is intended to be used in a "postproduction" phase (see resolvePaths method). Parameters:
startVertex
 the start vertexendVertex
 the end vertex Returns:
 the shortest path between start and end vertices.

getPaths
Returns the $k$ shortest simple paths in increasing order of weight. Specified by:
getPaths
in interfaceKShortestPathAlgorithm<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 endVertexIllegalArgumentException
 if the startVertex and the endVertex are the same verticesIllegalArgumentException
 if the startVertex or the endVertex is null
