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