Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class BhandariKDisjointShortestPaths<V,E>
java.lang.Object
org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm<V,E>
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$ 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.
-
Field Summary
Fields inherited from class org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm
originalGraph, pathList, workingGraph
-
Constructor Summary
ConstructorsConstructorDescriptionBhandariKDisjointShortestPaths
(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.protected void
transformGraph
(List<E> previousPath) Prepares the working graph for next iteration.Methods inherited from class org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm
getPaths
-
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
Description copied from class:BaseKDisjointShortestPathsAlgorithm
Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a precedingBaseKDisjointShortestPathsAlgorithm.calculateShortestPath(V, V)
call.- Specified by:
transformGraph
in classBaseKDisjointShortestPathsAlgorithm<V,
E> - Parameters:
previousPath
- the path found at the previous iteration.
-
calculateShortestPath
Description copied from class:BaseKDisjointShortestPathsAlgorithm
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).- Specified by:
calculateShortestPath
in classBaseKDisjointShortestPathsAlgorithm<V,
E> - Parameters:
startVertex
- the start vertexendVertex
- the end vertex- Returns:
- the shortest path between start and end vertices.
-