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 |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
|
ANY-NUMERICAL |
X coordinate of |
|
|
ANY-NUMERICAL |
Y coordinate of |
|
|
ANY-NUMERICAL |
X coordinate of |
|
|
ANY-NUMERICAL |
Y coordinate of |
Where:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations query¶
Parameter |
Type |
Description |
---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER
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