# pgRouting Manual (3.6)

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

- A* - Family of functions

- https://www.boost.org/libs/graph/doc/astar_search.html

- https://en.wikipedia.org/wiki/A*_search_algorithm

Indices and tables

- Index

- Search Page