Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class SuurballeKDisjointShortestPaths<V,E>
java.lang.Object
org.jgrapht.alg.shortestpath.SuurballeKDisjointShortestPaths<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
KShortestPathAlgorithm<V,
E>
An implementation of Suurballe algorithm for finding K edgedisjoint 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.
 Author:
 Assaf Mizrachi

Field Summary

Constructor Summary
ConstructorDescriptionSuurballeKDisjointShortestPaths
(Graph<V, E> graph) Creates a new instance of the algorithm. 
Method Summary
Modifier and TypeMethodDescriptioncalculateShortestPath
(V startVertex, V endVertex) Calculates the shortest paths for the current iteration.Returns the $k$ shortest simple paths in increasing order of weight.protected void
transformGraph
(List<E> previousPath) Prepares the working graph for next iteration.

Field Details

workingGraph
Graph on which shortest paths are searched. 
pathList

originalGraph


Constructor Details

SuurballeKDisjointShortestPaths
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
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
Calculates the shortest paths for the current iteration. Path is not final; rather, it is intended to be used in a "postproduction" phase (see resolvePaths method). Parameters:
startVertex
 the start vertexendVertex
 the end vertex Returns:
 the shortest path between start and end vertices.

getPaths
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:
IllegalArgumentException
 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 null
