Class DijkstraShortestPath<V,E>
- All Implemented Interfaces:
Distance<V>
,ShortestPath<V,
E>
Calculates distances and shortest paths using Dijkstra's
single-source-shortest-path algorithm. This is a lightweight
extension of DijkstraDistance
that also stores
path information, so that the shortest paths can be reconstructed.
The elements in the maps returned by
getIncomingEdgeMap
are ordered (that is, returned
by the iterator) by nondecreasing distance from source
.
- See Also:
-
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 estimaed distance) of the vertices for which distances are unknown.Nested classes/interfaces inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
DijkstraDistance.SourceData, DijkstraDistance.VertexComparator<V>
-
Field Summary
Fields inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
cached, g, max_distance, max_targets, nev, sourceMap
-
Constructor Summary
ConstructorsConstructorDescriptionDijkstraShortestPath
(Graph<V, E> g) Creates an instance ofDijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.DijkstraShortestPath
(Graph<V, E> g, boolean cached) Creates an instance ofDijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.Creates an instance ofDijkstraShortestPath
for the specified graph and the specified method of extracting weights from edges, which caches results locally.DijkstraShortestPath
(Graph<V, E> g, com.google.common.base.Function<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 TypeMethodDescriptiongetIncomingEdge
(V source, V target) Returns the last edge on a shortest path fromsource
totarget
, or null iftarget
is not reachable fromsource
.getIncomingEdgeMap
(V source) Returns aLinkedHashMap
which maps each vertex in the graph (including thesource
vertex) to the last edge on the shortest path from thesource
vertex.getIncomingEdgeMap
(V source, int numDests) Returns aLinkedHashMap
which maps each of the closestnumDests
vertices to thesource
vertex in the graph (including thesource
vertex) to the incoming edge along the path from that vertex.Returns aList
of the edges on the shortest path fromsource
totarget
, in order of their occurrence on this path.protected DijkstraDistance<V,
E>.SourceData getSourceData
(V source) Methods inherited from class edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
enableCaching, getDistance, getDistanceMap, getDistanceMap, getDistanceMap, getEdgesToCheck, reset, reset, setMaxDistance, setMaxTargets, singleSourceShortestPath
-
Constructor Details
-
DijkstraShortestPath
public DijkstraShortestPath(Graph<V, E> g, com.google.common.base.Function<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
-
DijkstraShortestPath
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
-
DijkstraShortestPath
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
-
DijkstraShortestPath
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
-
getSourceData
- Overrides:
getSourceData
in classDijkstraDistance<V,
E>
-
getIncomingEdge
Returns the last edge on a shortest path from
source
totarget
, or null iftarget
is not reachable fromsource
.If either vertex is not in the graph for which this instance was created, throws
IllegalArgumentException
.- Parameters:
source
- the vertex where the shortest path startstarget
- the vertex where the shortest path ends- Returns:
- the last edge on a shortest path from
source
totarget
or null iftarget
is not reachable fromsource
-
getIncomingEdgeMap
Returns a
LinkedHashMap
which maps each vertex in the graph (including thesource
vertex) to the last edge on the shortest path from thesource
vertex. The map's iterator will return the elements in order of increasing distance fromsource
.- Specified by:
getIncomingEdgeMap
in interfaceShortestPath<V,
E> - Parameters:
source
- the vertex from which distances are measured- Returns:
- a map from vertices to the last edge on the shortest path to that vertex
starting from
source
- See Also:
-
getPath
Returns aList
of the edges on the shortest path fromsource
totarget
, in order of their occurrence on this path. If either vertex is not in the graph for which this instance was created, throwsIllegalArgumentException
.- Parameters:
source
- the starting vertex for the path to generatetarget
- the ending vertex for the path to generate- Returns:
- the edges on the shortest path from
source
totarget
, in order of their occurrence
-
getIncomingEdgeMap
Returns a
LinkedHashMap
which maps each of the closestnumDests
vertices to thesource
vertex in the graph (including thesource
vertex) to the incoming edge along the path from that 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.- Parameters:
source
- the vertex from which distances are measurednumDests
- the number of vertices for which to measure distances- Returns:
- a map from each of the closest
numDests
vertices to the last edge on the shortest path to that vertex starting fromsource
- See Also:
-