- Type Parameters:
V- the graph vertex type
E- the graph edge type
- All Implemented Interfaces:
public class SuurballeKDisjointShortestPaths<V,E> extends ObjectAn 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.
- Assaf Mizrachi
All Methods Instance Methods Concrete Methods Modifier and Type Method Description
calculateShortestPath(V startVertex, V endVertex)Calculates the shortest paths for the current iteration.
getPaths(V startVertex, V endVertex, int k)Returns the $k$ shortest simple paths in increasing order of weight.
transformGraph(List<E> previousPath)Prepares the working graph for next iteration.
SuurballeKDisjointShortestPathsCreates a new instance of the algorithm.
transformGraphPrepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding
previousPath- the path found at the previous iteration.
calculateShortestPathCalculates 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).
startVertex- the start vertex
endVertex- the end vertex
- the shortest path between start and end vertices.
getPathsReturns the $k$ shortest simple paths in increasing order of weight.
- Specified by:
startVertex- source vertex of the calculated paths.
endVertex- target vertex of the calculated paths.
k- the number of shortest paths to return
- list of disjoint paths between the start vertex and the end vertex
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