Class BidirectionalAStarShortestPath<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - 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
    • Field Detail

      • 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 graph
        heuristic - 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 graph
        heuristic - heuristic that estimates distances between nodes
        heapSupplier - supplier of the preferable heap implementation
    • Method Detail

      • getPath

        public GraphPath<V,​E> getPath​(V source,
                                            V sink)
        Get a shortest path from a source vertex to a sink vertex.
        Parameters:
        source - the source vertex
        sink - the target vertex
        Returns:
        a shortest path or null if no path exists