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>
public class BhandariKDisjointShortestPaths<V,E> extends java.lang.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 Summary
Fields Modifier and Type Field Description protected Graph<V,E>
originalGraph
protected java.util.List<java.util.List<E>>
pathList
protected Graph<V,E>
workingGraph
Graph on which shortest paths are searched.
-
Constructor Summary
Constructors Constructor Description BhandariKDisjointShortestPaths(Graph<V,E> graph)
Creates a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected GraphPath<V,E>
calculateShortestPath(V startVertex, V endVertex)
Calculates the shortest paths for the current iteration.java.util.List<GraphPath<V,E>>
getPaths(V startVertex, V endVertex, int k)
Returns the $k$ shortest simple paths in increasing order of weight.protected void
transformGraph(java.util.List<E> previousPath)
Prepares the working graph for next iteration.
-
-
-
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.
-
-
Method Detail
-
transformGraph
protected void transformGraph(java.util.List<E> previousPath)
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
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 vertexendVertex
- the end vertex- Returns:
- the shortest path between start and end vertices.
-
getPaths
public java.util.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 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:
java.lang.IllegalArgumentException
- if the graph does not contain the startVertex or the endVertexjava.lang.IllegalArgumentException
- if the startVertex and the endVertex are the same verticesjava.lang.IllegalArgumentException
- if the startVertex or the endVertex is null
-
-