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

Combinations query

Column	Type	Default	Description
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.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Edges query as described above.
Combinations SQL	TEXT	Combinations 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