java.lang.Object
org.jgrapht.alg.shortestpath.DijkstraShortestPath<V,E>
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
An implementation of Dijkstra's
shortest path algorithm using a pairing heap by default. A custom heap implementation can by
specified during the construction time.
 Author:
 John V. Sichi

Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> 
Field Summary
Modifier and TypeFieldDescriptionThe underlying graph.protected static final String
Error message for reporting the existence of a negativeweight cycle.protected static final String
Error message for reporting that a sink vertex is missing.protected static final String
Error message for reporting that a source vertex is missing. 
Constructor Summary
ConstructorDescriptionDijkstraShortestPath
(Graph<V, E> graph) Constructs a new instance of the algorithm for a given graph.DijkstraShortestPath
(Graph<V, E> graph, double radius) Constructs a new instance of the algorithm for a given graph.DijkstraShortestPath
(Graph<V, E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance of the algorithm for a given graph.DijkstraShortestPath
(Graph<V, E> graph, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance of the algorithm for a given graph. 
Method Summary
Modifier and TypeMethodDescriptioncreateEmptyPath
(V source, V sink) Create an empty path.static <V,
E> GraphPath<V, E> findPathBetween
(Graph<V, E> graph, V source, V sink) Find a path between two vertices.Get a shortest path from a source vertex to a sink vertex.Compute all shortest paths starting from a single source vertex.double
getPathWeight
(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.

Field Details

GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negativeweight cycle. See Also:

GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing. See Also:

GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing. See Also:

graph
The underlying graph.


Constructor Details

DijkstraShortestPath
Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation. Parameters:
graph
 the graph

DijkstraShortestPath
Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation. Parameters:
graph
 the graphradius
 limit on path length, or Double.POSITIVE_INFINITY for unbounded search

DijkstraShortestPath
public DijkstraShortestPath(Graph<V, E> graph, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use the heap supplied by theheapSupplier
 Parameters:
graph
 the graphheapSupplier
 supplier of the preferable heap implementation

DijkstraShortestPath
public DijkstraShortestPath(Graph<V, E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance of the algorithm for a given graph. Parameters:
graph
 the graphradius
 limit on path length, or Double.POSITIVE_INFINITY for unbounded searchheapSupplier
 supplier of the preferable heap implementation


Method Details

findPathBetween
Find a path between two vertices. For a more advanced search (e.g. limited by radius or using another heap), use the constructor instead. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph to be searchedsource
 the vertex at which the path should startsink
 the vertex at which the path should end Returns:
 a shortest path, or null if no path exists

getPath
Get a shortest path from a source vertex to a sink vertex. Parameters:
source
 the source vertexsink
 the target vertex Returns:
 a shortest path or null if no path exists

getPaths
Compute all shortest paths starting from a single source vertex.Note that in the case of Dijkstra's algorithm it is more efficient to compute all singlesource shortest paths using this method than repeatedly invoking
getPath(Object, Object)
for the same source but different sink vertex. Specified by:
getPaths
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertex Returns:
 the shortest paths

getPathWeight
Get the weight of the shortest path from a source vertex to a sink vertex. ReturnsDouble.POSITIVE_INFINITY
if no path exists. Specified by:
getPathWeight
in interfaceShortestPathAlgorithm<V,
E>  Parameters:
source
 the source vertexsink
 the sink vertex Returns:
 the weight of the shortest path from a source vertex to a sink vertex, or
Double.POSITIVE_INFINITY
if no path exists

createEmptyPath
Create an empty path. Returns null if the source vertex is different than the target vertex. Parameters:
source
 the source vertexsink
 the sink vertex Returns:
 an empty path or null null if the source vertex is different than the target vertex
