Bidirectional A*  Family of functions  pgRouting Manual (3.4)
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