 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
DijkstraShortestPath
and BellmanFordShortestPath
.
The deltastepping algorithm is described in the paper: U. Meyer, P. Sanders, $\Delta$stepping: a parallelizable shortest path algorithm, Journal of Algorithms, Volume 49, Issue 1, 2003, Pages 114152, ISSN 01966774.
The $\Delta$stepping algorithm takes as input a weighted graph $G(V,E)$, a source node $s$ and a parameter $\Delta > 0$. Let $tent[v]$ be the best known shortest distance from $s$ to vertex $v\in V$. At the start of the algorithm, $tent[s]=0$, $tent[v]=\infty$ for $v\in V\setminus \{s\}$. The algorithm partitions vertices in a series of buckets $B=(B_0, B_1, B_2, \dots)$, where a vertex $v\in V$ is placed in bucket $B_{\lfloor\frac{tent[v]}{\Delta}\rfloor}$. During the execution of the algorithm, vertices in bucket $B_i$, for $i=0,1,2,\dots$, are removed onebyone. For each removed vertex $v$, and for all its outgoing edges $(v,w)$, the algorithm checks whether $tent[v]+c(v,w) < tent[w]$. If so, $w$ is removed from its current bucket, $tent[w]$ is updated ($tent[w]=tent[v]+c(v,w)$), and $w$ is placed into bucket $B_{\lfloor\frac{tent[w]}{\Delta}\rfloor}$. Parallelism is achieved by processing all vertices belonging to the same bucket concurrently. The algorithm terminates when all buckets are empty. At this stage the array $tent$ contains the minimal cost from $s$ to every vertex $v \in V$. For a more detailed description of the algorithm, refer to the aforementioned paper.
For a given graph $G(V,E)$ and parameter $\Delta$, let a $\Delta$path be a path of total weight at most $\Delta$ with no repeated edges. The time complexity of the algorithm is $O(\frac{(V + E + n_{\Delta} + m_{\Delta})}{p} + \frac{L}{\Delta}\cdot d\cdot l_{\Delta}\cdot \log n)$, where
 $n_{\Delta}$  number of vertex pairs $(u,v)$, where $u$ and $v$ are connected by some $\Delta$path.
 $m_{\Delta}$  number of vertex triples $(u,v^{\prime},v)$, where $u$ and $v^{\prime}$ are connected by some $\Delta$path and edge $(v^{\prime},v)$ has weight at most $\Delta$.
 $L$  maximum weight of a shortest path from selected source to any sink.
 $d$  maximum vertex degree.
 $l_{\Delta}$  maximum number of edges in a $\Delta$path $+1$.
For parallelization, this implementation relies on the ThreadPoolExecutor
which is
supplied to this algorithm from outside.
 Since:
 January 2018
 Author:
 Semen Chudakov

Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> 
Field Summary
Modifier and TypeFieldDescriptionThe underlying graph.protected static final String
Error message for reporting the existence of a negativeweight cycle.protected static final String
Error message for reporting that a sink vertex is missing.protected static final String
Error message for reporting that a source vertex is missing. 
Constructor Summary
ConstructorDescriptionDeltaSteppingShortestPath
(Graph<V, E> graph, double delta) Deprecated.DeltaSteppingShortestPath
(Graph<V, E> graph, double delta, int parallelism) Deprecated.DeltaSteppingShortestPath
(Graph<V, E> graph, double delta, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a given graph, delta andexecutor
.DeltaSteppingShortestPath
(Graph<V, E> graph, double delta, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Constructs a new instance of the algorithm for a given graph, delta,executor
andvertexComparator
.DeltaSteppingShortestPath
(Graph<V, E> graph, int parallelism) Deprecated.replaced withDeltaSteppingShortestPath(Graph, ThreadPoolExecutor)
DeltaSteppingShortestPath
(Graph<V, E> graph, ThreadPoolExecutor executor) Constructs a new instance of the algorithm for a given graph andexecutor
.DeltaSteppingShortestPath
(Graph<V, E> graph, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Constructs a new instance of the algorithm for a givengraph
,executor
andvertexComparator
. 
Method Summary
Modifier and TypeMethodDescriptioncreateEmptyPath
(V source, V sink) Create an empty path.Get a shortest path from a source vertex to a sink vertex.Compute all shortest paths starting from a single source vertex.double
getPathWeight
(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.

Field Details

GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negativeweight cycle. See Also:

GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing. See Also:

GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing. See Also:

graph
The underlying graph.


Constructor Details

DeltaSteppingShortestPath
Constructs a new instance of the algorithm for a given graph andexecutor
. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. For utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
. Parameters:
graph
 graphexecutor
 executor which will be used for parallelization

DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V, E> graph, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Constructs a new instance of the algorithm for a givengraph
,executor
andvertexComparator
. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. For utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
.vertexComparator
provided via this constructor is used to create instances ofConcurrentSkipListSet
for the individual buckets. This gives a gives a small performance benefit for shortest paths computation. Parameters:
graph
 graphexecutor
 executor which will be used for parallelizationvertexComparator
 comparator for vertices of thegraph

DeltaSteppingShortestPath
Deprecated.Constructs a new instance of the algorithm for a given graph, delta. Parameters:
graph
 the graphdelta
 bucket width

DeltaSteppingShortestPath
Constructs a new instance of the algorithm for a given graph, delta andexecutor
. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. For utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
. Parameters:
graph
 the graphdelta
 bucket widthexecutor
 executor which will be used for parallelization

DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V, E> graph, double delta, ThreadPoolExecutor executor, Comparator<V> vertexComparator) Constructs a new instance of the algorithm for a given graph, delta,executor
andvertexComparator
. It is up to a user of this algorithm to handle the creation and termination of the providedexecutor
. For utility methods to manage aThreadPoolExecutor
seeConcurrencyUtil
.vertexComparator
provided via this constructor is used to create instances ofConcurrentSkipListSet
for the individual buckets. This gives a gives a small performance benefit for shortest paths computation. Parameters:
graph
 the graphdelta
 bucket widthexecutor
 executor which will be used for parallelizationvertexComparator
 comparator for vertices of thegraph

DeltaSteppingShortestPath
Deprecated.replaced withDeltaSteppingShortestPath(Graph, ThreadPoolExecutor)
Constructs a new instance of the algorithm for a given graph, parallelism. Parameters:
graph
 the graphparallelism
 maximum number of threads used in the computations

DeltaSteppingShortestPath
Deprecated.Constructs a new instance of the algorithm for a given graph, delta, parallelism. If delta is $0.0$ it will be computed during the algorithm execution. In general if the value of $\frac{maximum edge weight}{maximum outdegree}$ is known beforehand, it is preferable to specify it via this constructor, because processing the whole graph to compute this value may significantly slow down the algorithm. Parameters:
graph
 the graphdelta
 bucket widthparallelism
 maximum number of threads used in the computations


Method Details

getPath
Get a shortest path from a source vertex to a sink vertex. Parameters:
source
 the source vertexsink
 the target vertex Returns:
 a shortest path or null if no path exists

getPaths
Compute all shortest paths starting from a single source vertex. Specified by:
getPaths
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertex Returns:
 the shortest paths

getPathWeight
Get the weight of the shortest path from a source vertex to a sink vertex. ReturnsDouble.POSITIVE_INFINITY
if no path exists. Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertexsink
 the sink vertex Returns:
 the weight of the shortest path from a source vertex to a sink vertex, or
Double.POSITIVE_INFINITY
if no path exists

createEmptyPath
Create an empty path. Returns null if the source vertex is different than the target vertex. Parameters:
source
 the source vertexsink
 the sink vertex Returns:
 an empty path or null null if the source vertex is different than the target vertex

DeltaSteppingShortestPath(Graph, double, ThreadPoolExecutor)