V
 the graph vertex typeE
 the graph edge typepublic class BhandariKDisjointShortestPaths<V,E> extends Object
The algorithm is running $k$ sequential BellmanFord iterations to find the shortest path at each step. Hence, yielding a complexity of $k$*O(BellmanFord).
Modifier and Type  Field and Description 

protected Graph<V,E> 
originalGraph 
protected Set<E> 
overlappingEdges 
protected List<List<E>> 
pathList 
protected Graph<V,E> 
workingGraph
Graph on which shortest paths are searched.

Constructor and Description 

BhandariKDisjointShortestPaths(Graph<V,E> graph)
Creates a new instance of the algorithm.

Modifier and Type  Method and Description 

protected GraphPath<V,E> 
calculateShortestPath(V startVertex,
V endVertex)
Calculates the shortest paths for the current iteration.

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(List<E> previousPath)
Prepares the working graph for next iteration.

protected Graph<V,E> workingGraph
protected Set<E> overlappingEdges
protected Graph<V,E> originalGraph
public BhandariKDisjointShortestPaths(Graph<V,E> graph)
graph
 graph on which shortest paths are searched.IllegalArgumentException
 if the graph is null.IllegalArgumentException
 if the graph is undirected.IllegalArgumentException
 if the graph is not simple.protected void transformGraph(List<E> previousPath)
calculateShortestPath(V, V)
call.previousPath
 the path found at the previous iteration.protected GraphPath<V,E> calculateShortestPath(V startVertex, V endVertex)
startVertex
 the start vertexendVertex
 the end vertexpublic List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
getPaths
in interface KShortestPathAlgorithm<V,E>
startVertex
 source vertex of the calculated paths.endVertex
 target vertex of the calculated paths.k
 the number of shortest paths to returnIllegalArgumentException
 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 nullCopyright © 2018. All rights reserved.