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 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<V>
cached, g, max_distance, max_targets, nev, sourceMap
Constructor and Description |
---|
DijkstraShortestPath(Graph<V,E> g)
Creates an instance of
DijkstraShortestPath for
the specified unweighted graph (that is, all weights 1) which
caches results locally. |
DijkstraShortestPath(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. |
DijkstraShortestPath(Graph<V,E> g,
com.google.common.base.Function<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. |
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 if
cached is true . |
Modifier and Type | Method and Description |
---|---|
E |
getIncomingEdge(V source,
V target)
Returns the last edge on a shortest path from
source
to target , or null if target is not
reachable from source . |
Map<V,E> |
getIncomingEdgeMap(V 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. |
LinkedHashMap<V,E> |
getIncomingEdgeMap(V source,
int numDests)
Returns a
LinkedHashMap which maps each of the closest
numDests vertices to the source vertex
in the graph (including the source vertex)
to the incoming edge along the path from that vertex. |
List<E> |
getPath(V source,
V 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(V source) |
enableCaching, getDistance, getDistanceMap, getDistanceMap, getDistanceMap, getEdgesToCheck, reset, reset, setMaxDistance, setMaxTargets, singleSourceShortestPath
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 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(Graph<V,E> g, com.google.common.base.Function<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.
g
- the graph on which distances will be calculatednev
- the class responsible for returning weights for edgespublic DijkstraShortestPath(Graph<V,E> 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(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.
g
- the graph on which distances will be calculatedcached
- specifies whether the results are to be cachedprotected DijkstraDistance.SourceData getSourceData(V source)
getSourceData
in class DijkstraDistance<V,E>
public E getIncomingEdge(V source, V 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
.
source
- the vertex where the shortest path startstarget
- the vertex where the shortest path endssource
to target
or null if target
is not reachable from source
public Map<V,E> getIncomingEdgeMap(V 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<V,E>
source
- the vertex from which distances are measuredsource
DijkstraDistance.getDistanceMap(Object,int)
,
DijkstraDistance.getDistance(Object,Object)
public List<E> getPath(V source, V 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
.source
- the starting vertex for the path to generatetarget
- the ending vertex for the path to generatesource
to target
,
in order of their occurrencepublic LinkedHashMap<V,E> getIncomingEdgeMap(V source, int numDests)
Returns a LinkedHashMap
which maps each of the closest
numDests
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 vertices for which to measure distancesnumDests
vertices
to the last edge on the shortest path to that vertex starting from source
getIncomingEdgeMap(Object)
,
getPath(Object,Object)
Copyright © 2015. All rights reserved.