Class BidirectionalAStarShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm<V,E>
-
- org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm<V,E>
-
- org.jgrapht.alg.shortestpath.BidirectionalAStarShortestPath<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,E>
public class BidirectionalAStarShortestPath<V,E> extends BaseBidirectionalShortestPathAlgorithm<V,E>
A bidirectional version of A* 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.
The algorithm was first introduced in Ira Sheldon Pohl. 1969. Bi-Directional and Heuristic Search in Path Problems. Ph.D. Dissertation. Stanford University, Stanford, CA, USA. AAI7001588.
The implementation uses two termination criteria depending on if the provided heuristic is consistent or not. Both criteria are based on the shortest path distance $\mu$ seen thus far in the search. Initially, in both cases the algorithm sets $\mu=\infty$. Whenever the search updates the information about the vertex $v$, it sets $\mu = min\{\mu; g_f(v) + g_b(v)\}$, where $g_f(v)$ is the current best-known path cost from $source$ to $sink$ and $g_b(v)$ is the current best-known path cost from $sink$ to $source$.
- See Also:
AStarShortestPath
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
BidirectionalAStarShortestPath.AStarSearchFrontier
Maintains search frontier during shortest path computation.(package private) class
BidirectionalAStarShortestPath.ConsistentTerminationCriterion
Termination criterion for the consistent heuristics.(package private) class
BidirectionalAStarShortestPath.InconsistentTerminationCriterion
Termination criterion for the inconsistent heuristics.(package private) class
BidirectionalAStarShortestPath.ReversedGraphHeuristic
Helper class for backward search, since it should operate on the reversed graph.(package private) class
BidirectionalAStarShortestPath.TerminationCriterion
Termination criterion for the heuristic search.-
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 AStarAdmissibleHeuristic<V>
backwardHeuristic
Heuristic used for backward search.private AStarAdmissibleHeuristic<V>
forwardHeuristic
Heuristic used for forward search.private java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,V>>
heapSupplier
-
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 BidirectionalAStarShortestPath(Graph<V,E> graph, AStarAdmissibleHeuristic<V> heuristic)
Constructs a new instance of the algorithm for a given graph and heuristic.BidirectionalAStarShortestPath(Graph<V,E> graph, AStarAdmissibleHeuristic<V> heuristic, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,V>> heapSupplier)
Constructs a new instance of the algorithm for a given graph, heuristic and heap supplier.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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
-
-
-
-
Field Detail
-
forwardHeuristic
private AStarAdmissibleHeuristic<V> forwardHeuristic
Heuristic used for forward search.
-
backwardHeuristic
private AStarAdmissibleHeuristic<V> backwardHeuristic
Heuristic used for backward search. In general $d(u,v)\neq d(v,u)$, e.g. in the directed graphs.
-
heapSupplier
private final java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,V>> heapSupplier
-
-
Constructor Detail
-
BidirectionalAStarShortestPath
public BidirectionalAStarShortestPath(Graph<V,E> graph, AStarAdmissibleHeuristic<V> heuristic)
Constructs a new instance of the algorithm for a given graph and heuristic.- Parameters:
graph
- the graphheuristic
- heuristic that estimates distances between nodes
-
BidirectionalAStarShortestPath
public BidirectionalAStarShortestPath(Graph<V,E> graph, AStarAdmissibleHeuristic<V> heuristic, java.util.function.Supplier<org.jheaps.AddressableHeap<java.lang.Double,V>> heapSupplier)
Constructs a new instance of the algorithm for a given graph, heuristic and heap supplier.- Parameters:
graph
- the graphheuristic
- heuristic that estimates distances between nodesheapSupplier
- supplier of the preferable heap implementation
-
-