org.jgrapht.alg.shortestpath

## Class SuurballeKDisjointShortestPaths<V,E>

• java.lang.Object
• 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 Object
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).

• Suurballe, J. W.; Tarjan, R. E. (1984), A quick method for finding shortest pairs of disjoint paths.
Author:
Assaf Mizrachi
• ### Field Detail

• #### workingGraph

protected Graph<V,E> workingGraph
Graph on which shortest paths are searched.
• #### pathList

protected List<List<E>> pathList
• #### overlappingEdges

protected Set<E> overlappingEdges
• #### originalGraph

protected Graph<V,E> originalGraph

• ### Method Detail

• #### transformGraph

protected void transformGraph(List<E> previousPath)
Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding calculateShortestPath(V, V) call.
Parameters:
previousPath - the path found at the previous iteration.
• #### calculateShortestPath

protected GraphPath<V,E> calculateShortestPath(V startVertex,
V endVertex)
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).
Parameters:
startVertex - the start vertex
endVertex - the end vertex
Returns:
the shortest path between start and end vertices.
• #### 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