Package com.jgalgo.alg.shortestpath

Class ShortestPathStBidirectionalDijkstra

  • All Implemented Interfaces:
    ShortestPathSt
    public class ShortestPathStBidirectionalDijkstra
extends ShortestPathStAbstract
    Compute the shortest path between a source and a target using bidirectional Dijkstra's algorithm.

    Different from the single source algorithm of Dijkstra, this algorithm uses two heaps and growing trees originated from the source and target vertices, instead of a single one. The algorithm terminate (roughly) when the two trees meet. In practice, this algorithm can be much faster than the single source algorithm, especially for large graphs.

    Author:
    Barak Ugav

    • Constructor Detail

      • ShortestPathStBidirectionalDijkstra

        public ShortestPathStBidirectionalDijkstra()
        Create a algorithm for computing a shortest path between a source and a target.

        Please prefer using ShortestPathSt.newInstance() to get a default implementation for the ShortestPathSt interface.