- Type Parameters:
V- the graph vertex type
E- the graph edge type
- All Implemented Interfaces:
public class BhandariKDisjointShortestPaths<V,E> extends ObjectAn 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.
- Assaf Mizrachi
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
calculateShortestPath(V startVertex, V endVertex)Calculates the shortest paths for the current iteration.
getPaths(V startVertex, V endVertex, int k)Returns the $k$ shortest simple paths in increasing order of weight.
transformGraph(List<E> previousPath)Prepares the working graph for next iteration.
BhandariKDisjointShortestPathsCreates a new instance of the algorithm.
transformGraphPrepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding
previousPath- the path found at the previous iteration.
calculateShortestPathCalculates 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).
startVertex- the start vertex
endVertex- the end vertex
- the shortest path between start and end vertices.
getPathsReturns the $k$ shortest simple paths in increasing order of weight.
- Specified by:
startVertex- source vertex of the calculated paths.
endVertex- target vertex of the calculated paths.
k- the number of shortest paths to return
- list of disjoint paths between the start vertex and the end vertex
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