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.