Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class BidirectionalDijkstraShortestPath<V,E>
java.lang.Object
org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm<V,E>
org.jgrapht.alg.shortestpath.BidirectionalDijkstraShortestPath<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
public final class BidirectionalDijkstraShortestPath<V,E>
extends BaseBidirectionalShortestPathAlgorithm<V,E>
A bidirectional version of Dijkstra's algorithm.
See the Wikipedia article for details and references about bidirectional search. This technique does not change the worst-case behavior of the algorithm but reduces, in some cases, the number of visited vertices in practice. This implementation alternatively constructs forward and reverse paths from the source and target vertices respectively.
This iterator can use a custom heap implementation, which can specified during the construction time. Pairing heap is used by default
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static class
Maintains search frontier during shortest path computation.Nested classes/interfaces inherited from class org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm
BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,
E> Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm
ShortestPathAlgorithm.SingleSourcePaths<V,
E> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate 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
ConstructorsConstructorDescriptionBidirectionalDijkstraShortestPath
(Graph<V, E> graph) Constructs a new instance for a specified graph.BidirectionalDijkstraShortestPath
(Graph<V, E> graph, double radius) Constructs a new instance for a specified graph.BidirectionalDijkstraShortestPath
(Graph<V, E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance for a specified graph.BidirectionalDijkstraShortestPath
(Graph<V, E> graph, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance for a specified graph. -
Method Summary
Methods inherited from class org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm
createPath
Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPaths, getPathWeight
-
Field Details
-
radius
private double radius -
heapSupplier
-
-
Constructor Details
-
BidirectionalDijkstraShortestPath
Constructs a new instance for a specified graph.- Parameters:
graph
- the input graph
-
BidirectionalDijkstraShortestPath
public BidirectionalDijkstraShortestPath(Graph<V, E> graph, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance for a specified graph. The constructed algorithm will use the heap supplied by theheapSupplier
.- Parameters:
graph
- the input graphheapSupplier
- supplier of the preferable heap implementation
-
BidirectionalDijkstraShortestPath
Constructs a new instance for a specified graph.- Parameters:
graph
- the input graphradius
- limit on path length, or Double.POSITIVE_INFINITY for unbounded search
-
BidirectionalDijkstraShortestPath
public BidirectionalDijkstraShortestPath(Graph<V, E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double, Pair<V, E>>> heapSupplier) Constructs a new instance for a specified graph. The constructed algorithm will use the heap supplied by theheapSupplier
.- Parameters:
graph
- the input 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), 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
Description copied from interface:ShortestPathAlgorithm
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
-