Class DijkstraShortestPath<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance<V,E>
-
- edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath<V,E>
-
- All Implemented Interfaces:
Distance<V>
,ShortestPath<V,E>
public class DijkstraShortestPath<V,E> extends DijkstraDistance<V,E> implements 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 fromsource
.- See Also:
DijkstraDistance
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
DijkstraShortestPath.SourcePathData
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
Constructors Constructor Description DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g)
Creates an instance ofDijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g, boolean cached)
Creates an instance ofDijkstraShortestPath
for the specified unweighted graph (that is, all weights 1) which caches results locally.DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g, org.apache.commons.collections4.Transformer<E,? extends java.lang.Number> nev)
Creates an instance ofDijkstraShortestPath
for the specified graph and the specified method of extracting weights from edges, which caches results locally.DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g, org.apache.commons.collections4.Transformer<E,? extends java.lang.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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description E
getIncomingEdge(V source, V target)
Returns the last edge on a shortest path fromsource
totarget
, or null iftarget
is not reachable fromsource
.java.util.Map<V,E>
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.java.util.LinkedHashMap<V,E>
getIncomingEdgeMap(V source, int numDests)
Returns aLinkedHashMap
which maps each of the closestnumDist
vertices to thesource
vertex in the graph (including thesource
vertex) to the incoming edge along the path from that vertex.java.util.List<E>
getPath(V source, V target)
Returns aList
of the edges on the shortest path fromsource
totarget
, in order of their occurrence on this path.protected DijkstraDistance.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 Detail
-
DijkstraShortestPath
public DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g, org.apache.commons.collections4.Transformer<E,? extends java.lang.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
public DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g, org.apache.commons.collections4.Transformer<E,? extends java.lang.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
-
DijkstraShortestPath
public DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g)
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
public DijkstraShortestPath(edu.uci.ics.jung.graph.Graph<V,E> g, boolean cached)
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 Detail
-
getSourceData
protected DijkstraDistance.SourceData getSourceData(V source)
- Overrides:
getSourceData
in classDijkstraDistance<V,E>
-
getIncomingEdge
public E getIncomingEdge(V source, V target)
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
.
-
getIncomingEdgeMap
public java.util.Map<V,E> getIncomingEdgeMap(V source)
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- See Also:
DijkstraDistance.getDistanceMap(Object,int)
,DijkstraDistance.getDistance(Object,Object)
-
getPath
public java.util.List<E> getPath(V source, V target)
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
.
-
getIncomingEdgeMap
public java.util.LinkedHashMap<V,E> getIncomingEdgeMap(V source, int numDests)
Returns a
LinkedHashMap
which maps each of the closestnumDist
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 vertics for which to measure distances- See Also:
getIncomingEdgeMap(Object)
,getPath(Object,Object)
-
-