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:
DijkstraShortestPath
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
BidirectionalDijkstraShortestPath.DijkstraSearchFrontier<V,E>
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
Fields Modifier and Type Field Description private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<V,E>>>
heapSupplier
private double
radius
-
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
Constructors Constructor Description BidirectionalDijkstraShortestPath(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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<V,E>>> heapSupplier)
Constructs a new instance for a specified graph.BidirectionalDijkstraShortestPath(Graph<V,E> graph, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,Pair<V,E>>> heapSupplier)
Constructs a new instance for a specified graph.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm
createPath
-
Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm
createEmptyPath, getPaths, getPathWeight
-
-
-
-
Constructor Detail
-
BidirectionalDijkstraShortestPath
public BidirectionalDijkstraShortestPath(Graph<V,E> graph)
Constructs a new instance for a specified graph.- Parameters:
graph
- the input graph
-
BidirectionalDijkstraShortestPath
public BidirectionalDijkstraShortestPath(Graph<V,E> graph, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.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
public BidirectionalDijkstraShortestPath(Graph<V,E> graph, double radius)
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, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.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 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), 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
-
-