# pgRouting Manual (3.0-rc1)

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

Previous versions of this page

- Supported versions: current(3.0) 2.6
- Unsupported versions: 2.5

## 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_sql: | an SQL query, which should return a set of rows with the following columns:

Column | Type | Default | Description
--- | --- | --- | ---
id | `ANY-INTEGER` |  | Identifier of the edge.
source | `ANY-INTEGER` |  | Identifier of the first end point vertex of the edge.
target | `ANY-INTEGER` |  | Identifier of the second end point vertex of the edge.

cost

`ANY-NUMERICAL`

Weight of the edge (source, target)

- When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost

`ANY-NUMERICAL`

-1

Weight of the edge (target, source),

- When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

x1 | `ANY-NUMERICAL` |  | X coordinate of source vertex.
y1 | `ANY-NUMERICAL` |  | Y coordinate of source vertex.
x2 | `ANY-NUMERICAL` |  | X coordinate of target vertex.
y2 | `ANY-NUMERICAL` |  | Y coordinate of target vertex.

Where:

ANY-INTEGER: | SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT

## Parameters

Parameter | Type | Description
--- | --- | ---
edges_sql | `TEXT` | Edges SQL query as described above.
start_vid | `ANY-INTEGER` | Starting vertex identifier.
start_vids | `ARRAY[ANY-INTEGER]` | Starting vertices identifierers.
end_vid | `ANY-INTEGER` | Ending vertex identifier.
end_vids | `ARRAY[ANY-INTEGER]` | Ending vertices identifiers.

directed

`BOOLEAN`

- Optional.
  - When `false` the graph is considered as Undirected.
  - Default is `true` which considers the graph as Directed.

heuristic

`INTEGER`

(optional). Heuristic number. Current valid values 0~5. Default `5`

> - 0: h(v) = 0 (Use this value to compare with pgr_dijkstra)
> - 1: h(v) abs(max(dx, dy))
> - 2: h(v) abs(min(dx, dy))
> - 3: h(v) = dx * dx + dy * dy
> - 4: h(v) = sqrt(dx * dx + dy * dy)
> - 5: h(v) = abs(dx) + abs(dy)

factor | `FLOAT` | (optional). For units manipulation. \(factor > 0\). Default `1`. see Factor
epsilon | `FLOAT` | (optional). For less restricted results. \(epsilon >= 1\). Default `1`.

## See Also

Indices and tables

- Index
- Search Page