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 type

E - the graph edge type

All Implemented Interfaces:

KShortestPathAlgorithm<V,E>

public class BhandariKDisjointShortestPaths<V,E>
extends BaseKDisjointShortestPathsAlgorithm<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 BaseKDisjointShortestPathsAlgorithm

originalGraph, pathList, workingGraph

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
protected GraphPath<V,E>	calculateShortestPath(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 BaseKDisjointShortestPathsAlgorithm

getPaths

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

BhandariKDisjointShortestPaths

public BhandariKDisjointShortestPaths(Graph<V,E> graph)

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

protected void transformGraph(List<E> previousPath)

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 preceding BaseKDisjointShortestPathsAlgorithm.calculateShortestPath(V, V) call.

Specified by:

transformGraph in class BaseKDisjointShortestPathsAlgorithm<V,E>

Parameters:

previousPath - the path found at the previous iteration.

calculateShortestPath

protected GraphPath<V,E> calculateShortestPath(V startVertex,
 V endVertex)

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 class BaseKDisjointShortestPathsAlgorithm<V,E>

Parameters:

startVertex - the start vertex

endVertex - the end vertex

Returns:

the shortest path between start and end vertices.