java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
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.
-
Nested Class Summary
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final double
Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
graph, GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
-
Constructor Summary
ConstructorsConstructorDescriptionDijkstraShortestPath
(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 TypeMethodDescriptionstatic <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.Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPathWeight
-
Field Details
-
radius
private final double radius -
heapSupplier
-
-
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 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> - Overrides:
getPaths
in classBaseShortestPathAlgorithm<V,
E> - Parameters:
source
- the source vertex- Returns:
- the shortest paths
-