V
 the graph vertex typeE
 the graph edge typepublic class DeltaSteppingShortestPath<V,E> extends Object
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
For parallelization, this implementation relies on the ExecutorService
.
ShortestPathAlgorithm.SingleSourcePaths<V,E>
Modifier and Type  Field and Description 

protected Graph<V,E> 
graph
The underlying graph.

protected static String 
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negativeweight cycle.

protected static String 
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.

protected static String 
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.

Constructor and Description 

DeltaSteppingShortestPath(Graph<V,E> graph)
Constructs a new instance of the algorithm for a given graph.

DeltaSteppingShortestPath(Graph<V,E> graph,
double delta)
Constructs a new instance of the algorithm for a given graph and delta.

DeltaSteppingShortestPath(Graph<V,E> graph,
double delta,
int parallelism)
Constructs a new instance of the algorithm for a given graph, delta, parallelism.

DeltaSteppingShortestPath(Graph<V,E> graph,
int parallelism)
Constructs a new instance of the algorithm for a given graph and parallelism.

Modifier and Type  Method and Description 

protected 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.

protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
protected final Graph<V,E> graph
public DeltaSteppingShortestPath(Graph<V,E> graph)
graph
 graphpublic DeltaSteppingShortestPath(Graph<V,E> graph, double delta)
graph
 the graphdelta
 bucket widthpublic DeltaSteppingShortestPath(Graph<V,E> graph, int parallelism)
graph
 the graphparallelism
 maximum number of threads used in the computationspublic DeltaSteppingShortestPath(Graph<V,E> graph, double delta, int parallelism)
graph
 the graphdelta
 bucket widthparallelism
 maximum number of threads used in the computationspublic GraphPath<V,E> getPath(V source, V sink)
source
 the source vertexsink
 the target vertexpublic ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
getPaths
in interface ShortestPathAlgorithm<V,E>
source
 the source vertexpublic double getPathWeight(V source, V sink)
Double.POSITIVE_INFINITY
if no path exists.getPathWeight
in interface ShortestPathAlgorithm<V,E>
source
 the source vertexsink
 the sink vertexDouble.POSITIVE_INFINITY
if no path existsprotected final GraphPath<V,E> createEmptyPath(V source, V sink)
source
 the source vertexsink
 the sink vertexCopyright © 2019. All rights reserved.