# Bidirectional A* - Family of functions¶

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

pgr_bdAstar - Bidirectional A* algorithm for obtaining paths.

pgr_bdAstarCost - Bidirectional A* algorithm to calculate the cost of the paths.

pgr_bdAstarCostMatrix - Bidirectional A* algorithm to calculate a cost matrix of paths.

## 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.

## See Also¶

Indices and tables