Class DijkstraDistance<V,E>
- All Implemented Interfaces:
Distance<V>
- Direct Known Subclasses:
DijkstraShortestPath
Calculates distances in a specified graph, using
Dijkstra's single-source-shortest-path algorithm. All edge weights
in the graph must be nonnegative; if any edge with negative weight is
found in the course of calculating distances, an
IllegalArgumentException
will be thrown.
(Note: this exception will only be thrown when such an edge would be
used to update a given tentative distance;
the algorithm does not check for negative-weight edges "up front".)
Distances and partial results are optionally cached (by this instance) for later reference. Thus, if the 10 closest vertices to a specified source vertex are known, calculating the 20 closest vertices does not require starting Dijkstra's algorithm over from scratch.
Distances are stored as double-precision values.
If a vertex is not reachable from the specified source vertex, no
distance is stored. This is new behavior with version 1.4;
the previous behavior was to store a value of
Double.POSITIVE_INFINITY
. This change gives the algorithm
an approximate complexity of O(kD log k), where k is either the number of
requested targets or the number of reachable vertices (whichever is smaller),
and D is the average degree of a vertex.
The elements in the maps returned by getDistanceMap
are ordered (that is, returned
by the iterator) by nondecreasing distance from source
.
Users are cautioned that distances calculated should be assumed to
be invalidated by changes to the graph, and should invoke reset()
when appropriate so that the distances can be recalculated.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected class
For a given source vertex, holds the estimated and final distances, tentative and final assignments of incoming edges on the shortest path from the source vertex, and a priority queue (ordered by estimated distance) of the vertices for which distances are unknown.protected static class
Compares according to distances, so that the BinaryHeap knows how to order the tree. -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected boolean
protected Hypergraph
<V, E> protected double
protected int
protected Map
<V, DijkstraDistance<V, E>.SourceData> -
Constructor Summary
ConstructorsConstructorDescriptionDijkstraDistance
(Graph<V, E> g) Creates an instance ofDijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.DijkstraDistance
(Graph<V, E> g, boolean cached) Creates an instance ofDijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.DijkstraDistance
(Hypergraph<V, E> g, com.google.common.base.Function<? super E, ? extends Number> nev) Creates an instance ofDijkstraShortestPath
for the specified graph and the specified method of extracting weights from edges, which caches results locally.DijkstraDistance
(Hypergraph<V, E> g, com.google.common.base.Function<? super E, ? extends Number> nev, boolean cached) Creates an instance ofDijkstraShortestPath
for the specified graph and the specified method of extracting weights from edges, which caches results locally if and only ifcached
istrue
. -
Method Summary
Modifier and TypeMethodDescriptionvoid
enableCaching
(boolean enable) Specifies whether or not this instance ofDijkstraShortestPath
should cache its results (final and partial) for future reference.getDistance
(V source, V target) Returns the length of a shortest path from the source to the target vertex, or null if the target is not reachable from the source.getDistanceMap
(V source) Returns aLinkedHashMap
which maps each vertex in the graph (including thesource
vertex) to its distance from thesource
vertex.getDistanceMap
(V source, int numDests) Returns aLinkedHashMap
which maps each of the closestnumDist
vertices to thesource
vertex in the graph (including thesource
vertex) to its distance from thesource
vertex.getDistanceMap
(V source, Collection<V> targets) Returns aMap
from each elementt
oftargets
to the shortest-path distance fromsource
tot
.protected Collection
<E> getEdgesToCheck
(V v) Returns the set of edges incident tov
that should be tested.protected DijkstraDistance<V,
E>.SourceData getSourceData
(V source) void
reset()
Clears all stored distances for this instance.void
Clears all stored distances for the specified source vertexsource
.void
setMaxDistance
(double max_dist) Allows the user to specify the maximum distance that this instance will calculate.void
setMaxTargets
(int max_targets) Allows the user to specify the maximum number of target vertices per source vertex for which this instance will calculate distances.protected LinkedHashMap
<V, Number> singleSourceShortestPath
(V source, Collection<V> targets, int numDests) Implements Dijkstra's single-source shortest-path algorithm for weighted graphs.
-
Field Details
-
g
-
nev
-
sourceMap
-
cached
protected boolean cached -
max_distance
protected double max_distance -
max_targets
protected int max_targets
-
-
Constructor Details
-
DijkstraDistance
public DijkstraDistance(Hypergraph<V, E> g, com.google.common.base.Function<? super E, ? extends Number> nev, boolean cached) Creates an instance of
DijkstraShortestPath
for the specified graph and the specified method of extracting weights from edges, which caches results locally if and only ifcached
istrue
.- Parameters:
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edgescached
- specifies whether the results are to be cached
-
DijkstraDistance
public DijkstraDistance(Hypergraph<V, E> g, com.google.common.base.Function<? super E, ? extends Number> nev) Creates an instance of
DijkstraShortestPath
for the specified graph and the specified method of extracting weights from edges, which caches results locally.- Parameters:
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edges
-
DijkstraDistance
Creates an instance of
DijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.- Parameters:
g
- the graph on which distances will be calculated
-
DijkstraDistance
Creates an instance of
DijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.- Parameters:
g
- the graph on which distances will be calculatedcached
- specifies whether the results are to be cached
-
-
Method Details
-
singleSourceShortestPath
protected LinkedHashMap<V,Number> singleSourceShortestPath(V source, Collection<V> targets, int numDests) Implements Dijkstra's single-source shortest-path algorithm for weighted graphs. Uses aMapBinaryHeap
as the priority queue, which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n = # of vertices). This algorithm will terminate when any of the following have occurred (in order of priority):- the distance to the specified target (if any) has been found
- no more vertices are reachable
- the specified # of distances have been found, or the maximum distance desired has been exceeded
- all distances have been found
- Parameters:
source
- the vertex from which distances are to be measuredtargets
- the set of vertices to which distances are to be measurednumDests
- the number of distances to measure- Returns:
- a mapping from vertex to the shortest distance from the source to each target
-
getSourceData
-
getEdgesToCheck
Returns the set of edges incident tov
that should be tested. By default, this is the set of outgoing edges for instances ofGraph
, the set of incident edges for instances ofHypergraph
, and is otherwise undefined.- Parameters:
v
- the vertex whose edges are to be checked- Returns:
- the set of edges incident to
v
that should be tested
-
getDistance
Returns the length of a shortest path from the source to the target vertex, or null if the target is not reachable from the source. If either vertex is not in the graph for which this instance was created, throwsIllegalArgumentException
.- Specified by:
getDistance
in interfaceDistance<V>
- Parameters:
source
- the vertex from which the distance totarget
is to be measuredtarget
- the vertex to which the distance fromsource
is to be measured- Returns:
- the distance between
source
andtarget
- See Also:
-
getDistanceMap
Returns aMap
from each elementt
oftargets
to the shortest-path distance fromsource
tot
.- Parameters:
source
- the vertex from which the distance to each target is to be measuredtargets
- the vertices to which the distance from the source is to be measured- Returns:
Map
from each element oftargets
to its distance fromsource
-
getDistanceMap
Returns a
LinkedHashMap
which maps each vertex in the graph (including thesource
vertex) to its distance from thesource
vertex. The map's iterator will return the elements in order of increasing distance fromsource
.The size of the map returned will be the number of vertices reachable from
source
.- Specified by:
getDistanceMap
in interfaceDistance<V>
- Parameters:
source
- the vertex from which distances are measured- Returns:
- a mapping from each vertex in the graph to its distance from
source
- See Also:
-
getDistanceMap
Returns a
LinkedHashMap
which maps each of the closestnumDist
vertices to thesource
vertex in the graph (including thesource
vertex) to its distance from thesource
vertex. Throws anIllegalArgumentException
ifsource
is not in this instance's graph, or ifnumDests
is either less than 1 or greater than the number of vertices in the graph.The size of the map returned will be the smaller of
numDests
and the number of vertices reachable fromsource
.- Parameters:
source
- the vertex from which distances are measurednumDests
- the number of vertices for which to measure distances- Returns:
- a mapping from the
numDests
vertices in the graph closest tosource
, to their distance fromsource
- See Also:
-
setMaxDistance
public void setMaxDistance(double max_dist) Allows the user to specify the maximum distance that this instance will calculate. Any vertices past this distance will effectively be unreachable from the source, in the sense that the algorithm will not calculate the distance to any vertices which are farther away than this distance. A negative value formax_dist
will ensure that no further distances are calculated.This can be useful for limiting the amount of time and space used by this algorithm if the graph is very large.
Note: if this instance has already calculated distances greater than
max_dist
, and the results are cached, those results will still be valid and available; this limit applies only to subsequent distance calculations.- Parameters:
max_dist
- the maximum distance that this instance will calculate- See Also:
-
setMaxTargets
public void setMaxTargets(int max_targets) Allows the user to specify the maximum number of target vertices per source vertex for which this instance will calculate distances. Once this threshold is reached, any further vertices will effectively be unreachable from the source, in the sense that the algorithm will not calculate the distance to any more vertices. A negative value formax_targets
will ensure that no further distances are calculated.This can be useful for limiting the amount of time and space used by this algorithm if the graph is very large.
Note: if this instance has already calculated distances to a greater number of targets than
max_targets
, and the results are cached, those results will still be valid and available; this limit applies only to subsequent distance calculations.- Parameters:
max_targets
- the maximum number of targets for which this instance will calculate distances- See Also:
-
reset
public void reset()Clears all stored distances for this instance. Should be called whenever the graph is modified (edge weights changed or edges added/removed). If the user knows that some currently calculated distances are unaffected by a change,reset(V)
may be appropriate instead.- See Also:
-
enableCaching
public void enableCaching(boolean enable) Specifies whether or not this instance ofDijkstraShortestPath
should cache its results (final and partial) for future reference.- Parameters:
enable
-true
if the results are to be cached, andfalse
otherwise
-
reset
Clears all stored distances for the specified source vertexsource
. Should be called whenever the stored distances from this vertex are invalidated by changes to the graph.- Parameters:
source
- the vertex for which stored distances should be cleared- See Also:
-