Package org.jgrapht.alg.shortestpath
Class DijkstraShortestPath<V,E>
- 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>
public final class DijkstraShortestPath<V,E> extends java.lang.Object
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
Fields Modifier and Type Field Description protected Graph<V,E>
graph
The underlying graph.protected static java.lang.String
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.protected static java.lang.String
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.protected static java.lang.String
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.
-
Constructor Summary
Constructors Constructor 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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<V,E>>> heapSupplier)
Constructs a new instance of the algorithm for a given graph.DijkstraShortestPath(Graph<V,E> graph, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<V,E>>> heapSupplier)
Constructs a new instance of the algorithm for a given graph.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
Field Detail
-
GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
protected static final java.lang.String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
Error message for reporting the existence of a negative-weight cycle.- See Also:
- Constant Field Values
-
GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
protected static final java.lang.String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
Error message for reporting that a source vertex is missing.- See Also:
- Constant Field Values
-
GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
protected static final java.lang.String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
Error message for reporting that a sink vertex is missing.- See Also:
- Constant Field Values
-
graph
protected final Graph<V,E> graph
The underlying graph.
-
-
Constructor Detail
-
DijkstraShortestPath
public DijkstraShortestPath(Graph<V,E> graph)
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
public DijkstraShortestPath(Graph<V,E> graph, double radius)
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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.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 Detail
-
findPathBetween
public static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph, V source, V sink)
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
public GraphPath<V,E> getPath(V source, V sink)
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
public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
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 single-source 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
public double getPathWeight(V source, V sink)
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
protected final GraphPath<V,E> createEmptyPath(V source, V sink)
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
-
-