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
- first by
- 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\)
- If there is no path from \(v\) to \(u\):
- 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.