public class DijkstraShortestPath extends DijkstraDistance implements ShortestPath
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
.
DijkstraDistance
Modifier and Type | Class and 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.
|
DijkstraDistance.SourceData, DijkstraDistance.VertexComparator
cached, dev, g, max_distance, max_targets, nev, sourceMap
Constructor and Description |
---|
DijkstraShortestPath(ArchetypeGraph g)
Creates an instance of
DijkstraShortestPath for
the specified unweighted graph (that is, all weights 1) which
caches results locally. |
DijkstraShortestPath(ArchetypeGraph g,
boolean cached)
Creates an instance of
DijkstraShortestPath for
the specified unweighted graph (that is, all weights 1) which
caches results locally. |
DijkstraShortestPath(ArchetypeGraph g,
NumberEdgeValue nev)
Creates an instance of
DijkstraShortestPath for
the specified graph and the specified method of extracting weights
from edges, which caches results locally. |
DijkstraShortestPath(ArchetypeGraph g,
NumberEdgeValue 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 if
cached is true . |
Modifier and Type | Method and Description |
---|---|
Edge |
getIncomingEdge(Vertex source,
Vertex target)
Returns the last edge on a shortest path from
source
to target , or null if target is not
reachable from source . |
java.util.Map |
getIncomingEdgeMap(Vertex source)
Returns a
LinkedHashMap which maps each vertex
in the graph (including the source vertex)
to the last edge on the shortest path from the
source vertex. |
java.util.LinkedHashMap |
getIncomingEdgeMap(Vertex source,
int numDests)
Returns a
LinkedHashMap which maps each of the closest
numDist vertices to the source vertex
in the graph (including the source vertex)
to the incoming edge along the path from that vertex. |
java.util.List |
getPath(Vertex source,
Vertex target)
Returns a
List of the edges on the shortest path from
source to target , in order of their
occurrence on this path. |
protected DijkstraDistance.SourceData |
getSourceData(ArchetypeVertex source) |
enableCaching, getDistance, getDistanceMap, getDistanceMap, getDistanceMap, getIncidentEdges, reset, reset, setMaxDistance, setMaxTargets, singleSourceShortestPath
public DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue 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 if
cached
is true
.
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edgescached
- specifies whether the results are to be cachedpublic DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev)
Creates an instance of DijkstraShortestPath
for
the specified graph and the specified method of extracting weights
from edges, which caches results locally.
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edgespublic DijkstraShortestPath(ArchetypeGraph g)
Creates an instance of DijkstraShortestPath
for
the specified unweighted graph (that is, all weights 1) which
caches results locally.
g
- the graph on which distances will be calculatedpublic DijkstraShortestPath(ArchetypeGraph g, boolean cached)
Creates an instance of DijkstraShortestPath
for
the specified unweighted graph (that is, all weights 1) which
caches results locally.
g
- the graph on which distances will be calculatedcached
- specifies whether the results are to be cachedprotected DijkstraDistance.SourceData getSourceData(ArchetypeVertex source)
getSourceData
in class DijkstraDistance
public Edge getIncomingEdge(Vertex source, Vertex target)
Returns the last edge on a shortest path from source
to target
, or null if target
is not
reachable from source
.
If either vertex is not in the graph for which this instance
was created, throws IllegalArgumentException
.
public java.util.Map getIncomingEdgeMap(Vertex source)
Returns a LinkedHashMap
which maps each vertex
in the graph (including the source
vertex)
to the last edge on the shortest path from the
source
vertex.
The map's iterator will return the elements in order of
increasing distance from source
.
getIncomingEdgeMap
in interface ShortestPath
source
- the vertex from which distances are measuredDijkstraDistance#getDistanceMap(Vertex,int)
,
DijkstraDistance#getDistance(Vertex,Vertex)
public java.util.List getPath(Vertex source, Vertex target)
List
of the edges on the shortest path from
source
to target
, in order of their
occurrence on this path.
If either vertex is not in the graph for which this instance
was created, throws IllegalArgumentException
.public java.util.LinkedHashMap getIncomingEdgeMap(Vertex source, int numDests)
Returns a LinkedHashMap
which maps each of the closest
numDist
vertices to the source
vertex
in the graph (including the source
vertex)
to the incoming edge along the path from that vertex. Throws
an IllegalArgumentException
if source
is not in this instance's graph, or if numDests
is
either less than 1 or greater than the number of vertices in the
graph.
source
- the vertex from which distances are measurednumDests
- the number of vertics for which to measure distancesgetIncomingEdgeMap(Vertex)
,
getPath(Vertex,Vertex)