V
 the graph vertex typeE
 the graph edge typepublic final class DijkstraShortestPath<V,E> extends Object
ShortestPathAlgorithm.SingleSourcePaths<V,E>
Modifier and Type  Field and Description 

protected Graph<V,E> 
graph
The underlying graph.

protected static String 
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negativeweight cycle.

protected static String 
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.

protected static String 
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.

Constructor and Description 

DijkstraShortestPath(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.

Modifier and Type  Method and Description 

protected GraphPath<V,E> 
createEmptyPath(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.

GraphPath<V,E> 
getPath(V source,
V sink)
Get a shortest path from a source vertex to a sink vertex.

ShortestPathAlgorithm.SingleSourcePaths<V,E> 
getPaths(V source)
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.

protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
protected final Graph<V,E> graph
public DijkstraShortestPath(Graph<V,E> graph)
graph
 the graphpublic DijkstraShortestPath(Graph<V,E> graph, double radius)
graph
 the graphradius
 limit on path length, or Double.POSITIVE_INFINITY for unbounded searchpublic DijkstraShortestPath(Graph<V,E> graph, Supplier<org.jheaps.AddressableHeap<Double,Pair<V,E>>> heapSupplier)
heapSupplier
graph
 the graphheapSupplier
 supplier of the preferable heap implementationpublic DijkstraShortestPath(Graph<V,E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double,Pair<V,E>>> heapSupplier)
graph
 the graphradius
 limit on path length, or Double.POSITIVE_INFINITY for unbounded searchheapSupplier
 supplier of the preferable heap implementationpublic static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph, V source, V sink)
V
 the graph vertex typeE
 the graph edge typegraph
 the graph to be searchedsource
 the vertex at which the path should startsink
 the vertex at which the path should endpublic GraphPath<V,E> getPath(V source, V sink)
source
 the source vertexsink
 the target vertexpublic ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
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.
getPaths
in interface ShortestPathAlgorithm<V,E>
source
 the source vertexpublic double getPathWeight(V source, V sink)
Double.POSITIVE_INFINITY
if no path exists.getPathWeight
in interface ShortestPathAlgorithm<V,E>
source
 the source vertexsink
 the sink vertexDouble.POSITIVE_INFINITY
if no path existsprotected final GraphPath<V,E> createEmptyPath(V source, V sink)
source
 the source vertexsink
 the sink vertexCopyright © 2019. All rights reserved.