Class DeltaSteppingShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.DeltaSteppingShortestPath<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
public class DeltaSteppingShortestPath<V,E> extends java.lang.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 outperformsDijkstraShortestPath
andBellmanFordShortestPath
.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
ExecutorService
.- 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
Fields Modifier and Type Field Description protected Graph<V,E>
graph
The underlying graph.protected static java.lang.String
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.protected static java.lang.String
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.protected static java.lang.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)
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.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
Field Detail
-
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
protected static final java.lang.String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.- See Also:
- Constant Field Values
-
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
protected static final java.lang.String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.- See Also:
- Constant Field Values
-
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
protected static final java.lang.String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.- See Also:
- Constant Field Values
-
graph
protected final Graph<V,E> graph
The underlying graph.
-
-
Constructor Detail
-
DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V,E> graph)
Constructs a new instance of the algorithm for a given graph.- Parameters:
graph
- graph
-
DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V,E> graph, double delta)
Constructs a new instance of the algorithm for a given graph and delta.- Parameters:
graph
- the graphdelta
- bucket width
-
DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V,E> graph, int parallelism)
Constructs a new instance of the algorithm for a given graph and parallelism.- Parameters:
graph
- the graphparallelism
- maximum number of threads used in the computations
-
DeltaSteppingShortestPath
public DeltaSteppingShortestPath(Graph<V,E> graph, double delta, int parallelism)
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 Detail
-
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 vertexsink
- the target vertex- Returns:
- a shortest path or null if no path exists
-
getPaths
public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
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
public double getPathWeight(V source, V sink)
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
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 vertexsink
- the sink vertex- Returns:
- an empty path or null null if the source vertex is different than the target vertex
-
-