Class SuurballeKDisjointShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm<V,E>
org.jgrapht.alg.shortestpath.SuurballeKDisjointShortestPaths<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
KShortestPathAlgorithm<V,E>

public class SuurballeKDisjointShortestPaths<V,E> extends BaseKDisjointShortestPathsAlgorithm<V,E>
An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths. The algorithm determines the k disjoint shortest simple paths in increasing order of weight. Only directed simple graphs are allowed.

The algorithm is running k sequential Dijkstra iterations to find the shortest path at each step. Hence, yielding a complexity of k*O(Dijkstra).

For further reference see Wikipedia page

  • Suurballe, J. W.; Tarjan, R. E. (1984), A quick method for finding shortest pairs of disjoint paths.