Bidirectional A* - Family of functions - pgRouting Manual (3.4)
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 \(\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