pgr_bdAstar - Bi-directional A* Shortest Path¶
Name¶
pgr_bdAstar
- Returns the shortest path using Bidirectional A* algorithm.
Synopsis¶
This is a bi-directional A* search algorithm. It searchs from the source toward the distination and at the same time from the destination to the source and terminates whe these to searchs meet in the middle. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.
pgr_costResult[] pgr_bdAstar(sql text, source integer, target integer,
directed boolean, has_rcost boolean);
Description¶
sql: | a SQL query, which should return a set of rows with the following columns: SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table
|
||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
source: |
|
||||||||||||||||||
target: |
|
||||||||||||||||||
directed: |
|
||||||||||||||||||
has_rcost: | if |
Returns set of pgr_costResult[]:
seq: | row sequence |
---|---|
id1: | node ID |
id2: | edge ID (-1 for the last row) |
cost: | cost to traverse from id1 using id2 |
Warning
You must reconnect to the database after CREATE EXTENSION pgrouting
. Otherwise the function will return Error computing path: std::bad_alloc
.
History
- New in version 2.0.0
Examples¶
- Without
reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_bdAstar(
'SELECT id, source, target, cost, x1, y1, x2, y2 FROM edge_table',
4, 10, false, false
);
seq | node | edge | cost
-----+------+------+------
0 | 4 | 3 | 0
1 | 3 | 5 | 1
2 | 6 | 11 | 1
3 | 11 | 12 | 0
4 | 10 | -1 | 0
(5 rows)
- With
reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_bdAstar(
'SELECT id, source, target, cost, x1, y1, x2, y2, reverse_cost FROM edge_table',
4, 10, true, true
);
seq | node | edge | cost
-----+------+------+------
0 | 4 | 3 | 1
1 | 3 | 5 | 1
2 | 6 | 8 | 1
3 | 5 | 10 | 1
4 | 10 | -1 | 0
(5 rows)
The queries use the Sample Data network.