Bidirectional A* - Family of functions - pgRouting Manual (3.3)

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