# Bidirectional A* - Family of functions¶

The bidirectional A* (pronounced “A Star”) algorithm is based on the A* algorithm.

## Description¶

Based on A* algorithm, the bidirectional search finds a shortest path from a starting vertex (start_vid) to an ending vertex (end_vid). It runs two simultaneous searches: one forward from the start_vid, and one backward from the end_vid, stopping when the two meet in the middle. This implementation can be used with a directed graph and an undirected graph.

The main Characteristics are:

• Process works for directed and undirected graphs.

• Ordering is:

• first by start_vid (if exists)

• then by end_vid

• Values are returned when there is a path.

• Let $$v$$ and $$u$$ be nodes on the graph:

• If there is no path from $$v$$ to $$u$$:

• no corresponding row is returned

• agg_cost from $$v$$ to $$u$$ is $$\infty$$

• There is no path when $$v = u$$ therefore

• no corresponding row is returned

• agg_cost from v to u is $$0$$

• When $$(x,y)$$ coordinates for the same vertex identifier differ:

• A random selection of the vertex’s $$(x,y)$$ coordinates is used.

• Running time: $$O((E + V) * \log V)$$

• For large graphs where there is a path bewtween the starting vertex and ending vertex:

• It is expected to terminate faster than pgr_astar

See heuristics available and factor handling.