Bidirectional A* - Family of functions

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

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