org.jgrapht.alg.shortestpath

Class BhandariKDisjointShortestPaths<V,E>

java.lang.Object

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 Object
implements 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.

Since:

February 12, 2018

Author:

Assaf Mizrachi

Constructor Summary

Constructors

Constructor and Description
BhandariKDisjointShortestPaths(Graph<V,E> graph) Creates an object to calculate $k$ disjoint shortest paths between the start vertex and others vertices.

Method Summary

Modifier and Type	Method and Description
List<GraphPath<V,E>>	getPaths(V startVertex, V endVertex, int k) Returns the $k$ shortest simple paths in increasing order of weight.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.interfaces.KShortestPathAlgorithm

getPaths

Constructor Detail

BhandariKDisjointShortestPaths

public BhandariKDisjointShortestPaths(Graph<V,E> graph)

Creates an object to calculate $k$ disjoint shortest paths between the start vertex and others vertices.

Parameters:

graph - graph on which shortest paths are searched.

Throws:

IllegalArgumentException - if nPaths is negative or 0.

IllegalArgumentException - if the graph is null.

IllegalArgumentException - if the graph is undirected.

Method Detail

getPaths

public 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 interface KShortestPathAlgorithm<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:

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