# Class DeltaSteppingShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.DeltaSteppingShortestPath<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ShortestPathAlgorithm<V,E>

public class DeltaSteppingShortestPath<V,E> extends Object
Parallel implementation of a single-source shortest path algorithm: the delta-stepping algorithm. The algorithm computes single source shortest paths in a graphs with non-negative edge weights. When using multiple threads, this implementation typically outperforms DijkstraShortestPath and BellmanFordShortestPath.

The delta-stepping 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 114-152, ISSN 0196-6774.

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 one-by-one. 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 classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,E>
• ## Field Summary

Fields
Modifier and Type
Field
Description
protected final Graph<V,E>
graph
The underlying graph.
protected static final String
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.
protected static final String
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.
protected static final String
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.
• ## Constructor Summary

Constructors
Constructor
Description
DeltaSteppingShortestPath(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 and executor.
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 and vertexComparator.
DeltaSteppingShortestPath(Graph<V,E> graph, int parallelism)
Deprecated.
DeltaSteppingShortestPath(Graph<V,E> graph, ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a given graph and executor.
DeltaSteppingShortestPath(Graph<V,E> graph, ThreadPoolExecutor executor, Comparator<V> vertexComparator)
Constructs a new instance of the algorithm for a given graph, executor and vertexComparator.
• ## Method Summary

Modifier and Type
Method
Description
protected final GraphPath<V,E>
createEmptyPath(V source, V sink)
Create an empty path.
GraphPath<V,E>
getPath(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,E>
getPaths(V source)
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.

### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ## Field Details

• ### GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.
• ### GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.
• ### GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.
• ### graph

protected final Graph<V,E> graph
The underlying graph.
• ## Constructor Details

• ### DeltaSteppingShortestPath

Constructs a new instance of the algorithm for a given graph and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. For utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
Parameters:
graph - graph
executor - 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 given graph, executor and vertexComparator. It is up to a user of this algorithm to handle the creation and termination of the provided executor. For utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil. vertexComparator provided via this constructor is used to create instances of ConcurrentSkipListSet for the individual buckets. This gives a gives a small performance benefit for shortest paths computation.
Parameters:
graph - graph
executor - executor which will be used for parallelization
vertexComparator - comparator for vertices of the graph
• ### DeltaSteppingShortestPath

public DeltaSteppingShortestPath(Graph<V,E> graph, double delta)
Deprecated.
Constructs a new instance of the algorithm for a given graph, delta.
Parameters:
graph - the graph
delta - bucket width
• ### DeltaSteppingShortestPath

public DeltaSteppingShortestPath(Graph<V,E> graph, double delta, ThreadPoolExecutor executor)
Constructs a new instance of the algorithm for a given graph, delta and executor. It is up to a user of this algorithm to handle the creation and termination of the provided executor. For utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil.
Parameters:
graph - the graph
delta - bucket width
executor - 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 and vertexComparator. It is up to a user of this algorithm to handle the creation and termination of the provided executor. For utility methods to manage a ThreadPoolExecutor see ConcurrencyUtil. vertexComparator provided via this constructor is used to create instances of ConcurrentSkipListSet for the individual buckets. This gives a gives a small performance benefit for shortest paths computation.
Parameters:
graph - the graph
delta - bucket width
executor - executor which will be used for parallelization
vertexComparator - comparator for vertices of the graph
• ### DeltaSteppingShortestPath

public DeltaSteppingShortestPath(Graph<V,E> graph, int parallelism)
Deprecated.
Constructs a new instance of the algorithm for a given graph, parallelism.
Parameters:
graph - the graph
parallelism - maximum number of threads used in the computations
• ### DeltaSteppingShortestPath

public DeltaSteppingShortestPath(Graph<V,E> graph, double delta, int parallelism)
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 graph
delta - bucket width
parallelism - maximum number of threads used in the computations
• ## Method Details

• ### getPath

public GraphPath<V,E> getPath(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.
Parameters:
source - the source vertex
sink - the target vertex
Returns:
a shortest path or null if no path exists
• ### getPaths

public  getPaths(V source)
Compute all shortest paths starting from a single source vertex.
Specified by:
getPaths in interface ShortestPathAlgorithm<V,E>
Parameters:
source - the source vertex
Returns:
the shortest paths
• ### getPathWeight

public double getPathWeight(V source, V sink)
Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
Specified by:
getPathWeight in interface ShortestPathAlgorithm<V,E>
Parameters:
source - the source vertex
sink - 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

protected final GraphPath<V,E> createEmptyPath(V source, V sink)
Create an empty path. Returns null if the source vertex is different than the target vertex.
Parameters:
source - the source vertex
sink - the sink vertex
Returns:
an empty path or null null if the source vertex is different than the target vertex