Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
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 typeE
- 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.
-
-
Field Summary
Fields Modifier and Type Field Description private ShortestPathAlgorithm.SingleSourcePaths<V,E>
singleSourcePaths
-
Fields inherited from class org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm
originalGraph, pathList, workingGraph
-
-
Constructor Summary
Constructors Constructor Description SuurballeKDisjointShortestPaths(Graph<V,E> graph)
Creates a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected GraphPath<V,E>
calculateShortestPath(V startVertex, V endVertex)
Calculates the shortest paths for the current iteration.protected void
transformGraph(java.util.List<E> previousPath)
Prepares the working graph for next iteration.-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm
getPaths
-
-
-
-
Field Detail
-
singleSourcePaths
private ShortestPathAlgorithm.SingleSourcePaths<V,E> singleSourcePaths
-
-
Constructor Detail
-
SuurballeKDisjointShortestPaths
public SuurballeKDisjointShortestPaths(Graph<V,E> graph)
Creates a new instance of the algorithm.- Parameters:
graph
- graph on which shortest paths are searched.- Throws:
java.lang.IllegalArgumentException
- if the graph is null.java.lang.IllegalArgumentException
- if the graph is undirected.java.lang.IllegalArgumentException
- if the graph is not simple.
-
-
Method Detail
-
transformGraph
protected void transformGraph(java.util.List<E> previousPath)
Description copied from class:BaseKDisjointShortestPathsAlgorithm
Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a precedingBaseKDisjointShortestPathsAlgorithm.calculateShortestPath(V, V)
call.- Specified by:
transformGraph
in classBaseKDisjointShortestPathsAlgorithm<V,E>
- Parameters:
previousPath
- the path found at the previous iteration.
-
calculateShortestPath
protected GraphPath<V,E> calculateShortestPath(V startVertex, V endVertex)
Description copied from class:BaseKDisjointShortestPathsAlgorithm
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).- Specified by:
calculateShortestPath
in classBaseKDisjointShortestPathsAlgorithm<V,E>
- Parameters:
startVertex
- the start vertexendVertex
- the end vertex- Returns:
- the shortest path between start and end vertices.
-
-