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¶
Parameter 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge (



ANYNUMERICAL 
1 
Weight of the edge (


ANYNUMERICAL 
X coordinate of 


ANYNUMERICAL 
Y coordinate of 


ANYNUMERICAL 
X coordinate of 


ANYNUMERICAL 
Y coordinate of 
Where:
 ANYINTEGER
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations query¶
Parameter 
Type 
Description 


ANYINTEGER 
Identifier of the departure vertex. 

ANYINTEGER 
Identifier of the arrival vertex. 
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