Supported versions: latest (3.6) 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5

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 $\mathrm{\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)\ast \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