Class BidirectionalAStarShortestPath<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
ShortestPathAlgorithm<V,
E>
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
Maintains search frontier during shortest path computation.(package private) class
Termination criterion for the consistent heuristics.(package private) class
Termination criterion for the inconsistent heuristics.(package private) class
Helper class for backward search, since it should operate on the reversed graph.(package private) class
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
FieldsModifier and TypeFieldDescriptionprivate AStarAdmissibleHeuristic
<V> Heuristic used for backward search.private AStarAdmissibleHeuristic
<V> Heuristic used for forward search.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
ConstructorsConstructorDescriptionBidirectionalAStarShortestPath
(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, Supplier<org.jheaps.AddressableHeap<Double, V>> heapSupplier) Constructs a new instance of the algorithm for a given graph, heuristic and heap supplier. -
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
-
forwardHeuristic
Heuristic used for forward search. -
backwardHeuristic
Heuristic used for backward search. In general $d(u,v)\neq d(v,u)$, e.g. in the directed graphs. -
heapSupplier
-
-
Constructor Details
-
BidirectionalAStarShortestPath
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, Supplier<org.jheaps.AddressableHeap<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
-
-
Method Details
-
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
-