Package com.jgalgo.alg.shortestpath

Class ShortestPathStBidirectionalDijkstra

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathStAbstract

com.jgalgo.alg.shortestpath.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 Summary

Constructors

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

Method Summary

Methods inherited from class com.jgalgo.alg.shortestpath.ShortestPathStAbstract

computeShortestPathAndWeight

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.jgalgo.alg.shortestpath.ShortestPathSt

computeShortestPath

Constructor Details

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.