Bidirectional A*  Family of functions¶
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.
Previous versions of this page
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 is done only on edges with positive costs.
Values are returned when there is a path.
When the starting vertex and ending vertex are the same, there is no path.
The agg_cost the non included values (v, v) is 0
When the starting vertex and ending vertex are the different and there is no path:
The agg_cost the non included values (u, v) is \(\infty\)
Running time (worse case scenario): \(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
Signatures¶
 edges_sql
an SQL query, which should return a set of rows with the following columns:
Column 
Type 
Default 
Description 

id 

Identifier of the edge. 

source 

Identifier of the first end point vertex of the edge. 

target 

Identifier of the second end point vertex of the edge. 

cost 

Weight of the edge (source, target)


reverse_cost 

1 
Weight of the edge (target, source),

x1 

X coordinate of source vertex. 

y1 

Y coordinate of source vertex. 

x2 

X coordinate of target vertex. 

y2 

Y coordinate of target vertex. 
Where:
 ANYINTEGER
SMALLINT, INTEGER, BIGINT
 ANYNUMERICAL
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Parameters¶
Parameter 
Type 
Description 

edges_sql 

Edges SQL query as described above. 
start_vid 

Starting vertex identifier. 
start_vids 

Starting vertices identifierers. 
end_vid 

Ending vertex identifier. 
end_vids 

Ending vertices identifiers. 
directed 


heuristic 

(optional). Heuristic number. Current valid values 0~5. Default

factor 

(optional). For units manipulation. \(factor > 0\). Default 
epsilon 

(optional). For less restricted results. \(epsilon >= 1\). Default 