Package com.jgalgo.alg.shortestpath

Class ShortestPathStBidirectionalBfs

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathStAbstract

com.jgalgo.alg.shortestpath.ShortestPathStBidirectionalBfs

All Implemented Interfaces:

ShortestPathSt

public class ShortestPathStBidirectionalBfs
extends ShortestPathStAbstract

Compute the shortest path between a source and a target using bidirectional breadth-first search.

The algorithm can be used with cardinality weight functions only, similar to ShortestPathSingleSourceCardinality. Different from the single source algorithm, this algorithm uses two BFS originated from the source and target vertices, instead of a single BFS. The algorithm terminate (roughly) when the two BFS trees meet. In practice, this algorithm can be much faster than the single source algorithm, especially for large graphs.

Author:

Barak Ugav

See Also:

• BfsIter

Constructor Summary

Constructors

Constructor	Description
ShortestPathStBidirectionalBfs()	Create a algorithm for computing a shortest path between a source and a target with respect to a cardinality weight function.

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

ShortestPathStBidirectionalBfs

public ShortestPathStBidirectionalBfs()

Create a algorithm for computing a shortest path between a source and a target with respect to a cardinality weight function.

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