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.
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 query¶
 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
Combinations query¶
Column 
Type 
Default 
Description 

source 

Identifier of the first end point vertex of the edge. 

target 

Identifier of the second end point vertex of the edge. 
Where:
 ANYINTEGER
SMALLINT, INTEGER, BIGINT
Parameters¶
Parameter 
Type 
Description 

Edges SQL 

Edges query as described above. 
Combinations SQL 

Combinations 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 
See Also¶
Indices and tables