# pgRouting Manual (2.1.0)

## 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

id: | `int4` identifier of the edge
source: | `int4` identifier of the source vertex
target: | `int4` identifier of the target vertex
cost: | `float8` value, of the edge traversal cost. A negative cost will prevent the edge from being inserted in the graph.
x1: | `x` coordinate of the start point of the edge
y1: | `y` coordinate of the start point of the edge
x2: | `x` coordinate of the end point of the edge
y2: | `y` coordinate of the end point of the edge
reverse_cost: | (optional) the cost for the reverse traversal of the edge. This is only used when the `directed` and `has_rcost` parameters are `true` (see the above remark about negative costs).

source: | `int4` id of the start point
target: | `int4` id of the end point
directed: | `true` if the graph is directed
has_rcost: | if `true`, the `reverse_cost` column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

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.

## See Also

- pgr_costResult[]
- pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path
- http://en.wikipedia.org/wiki/Bidirectional_search
- http://en.wikipedia.org/wiki/A*_search_algorithm