# pgr_aStar¶

## Name¶

pgr_aStar — Returns the shortest path using A* algorithm.

## Synopsis¶

The A* (pronounced “A Star”) algorithm is based on Dijkstra’s algorithm with a heuristic that allow it to solve most shortest path problems by evaluation only a sub-set of the overall graph.

## Characteristics¶

The main Characteristics are:

• Process is done only on edges with positive costs.
• Vertices of the graph are:
• positive when it belongs to the edges_sql
• negative when it belongs to the points_sql
• 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 ∞
• When (x,y) coordinates for the same vertex identifier differ:
• A random selection of the vertex’s (x,y) coordinates is used.
• Running time: $$O((E + V) * \log V)$$

## Signature Summary¶

pgr_aStar(edges_sql, start_vid, end_vid)
pgr_aStar(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)


Note

This signature is deprecated

pgr_aStar(sql, source integer, target integer, directed boolean, has_rcost boolean)
RETURNS SET OF pgr_costResult


## Signatures¶

### Minimal Signature¶

pgr_aStar(edges_sql, start_vid, end_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)

Example: Using the defaults
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, 12);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 |        1 |    2 |    4 |    1 |        0
2 |        2 |    5 |    8 |    1 |        1
3 |        3 |    6 |    9 |    1 |        2
4 |        4 |    9 |   15 |    1 |        3
5 |        5 |   12 |   -1 |    0 |        4
(5 rows)


### Complete Signature¶

pgr_aStar(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)

Example: Setting a Heuristic
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, 12, heuristic := 1);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 |        1 |    2 |    4 |    1 |        0
2 |        2 |    5 |    8 |    1 |        1
3 |        3 |    6 |    9 |    1 |        2
4 |        4 |    9 |   15 |    1 |        3
5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, 12, heuristic := 2);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 |        1 |    2 |    4 |    1 |        0
2 |        2 |    5 |    8 |    1 |        1
3 |        3 |    6 |    9 |    1 |        2
4 |        4 |    9 |   15 |    1 |        3
5 |        5 |   12 |   -1 |    0 |        4
(5 rows)


## Description of the Signatures¶

Note

The following only aplies to the new signature(s)

### Description of the edges_sql 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 SMALLINT, INTEGER, BIGINT, REAL, FLOAT

### Description of the parameters of the signatures¶

Parameter Type Description
edges_sql TEXT Edges SQL query as described above.
start_vid ANY-INTEGER Starting vertex identifier.
end_vid ANY-INTEGER Ending vertex identifier.
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.
epsilon FLOAT (optional). For less restricted results. $$factor >= 1$$. Default 1.

### Description of the return values¶

Returns set of (seq, path_seq, node, edge, cost, agg_cost)

Column Type Description
seq INTEGER Row sequence.
path_seq INTEGER Path sequence that indicates the relative position on the path.
node BIGINT
Identifier of the node:
• A positive value indicates the node is a vertex of edges_sql.
• A negative value indicates the node is a point of points_sql.
edge BIGINT
Identifier of the edge used to go from node to the next node in the path sequence.
• -1 for the last row in the path sequence.
cost FLOAT
Cost to traverse from node using edge to the next node in the path sequence.
• 0 for the last row in the path sequence.
agg_cost FLOAT
Aggregate cost from start_vid to node.
• 0 for the first row in the path sequence.

Analysis 1

Working with cost/reverse_cost as length in degrees, x/y in lat/lon: Factor = 1 (no need to change units)

Analysis 2

Working with cost/reverse_cost as length in meters, x/y in lat/lon: Factor = would depend on the location of the points:

latitude conversion Factor
45 1 longitude degree is 78846.81 m 78846
0 1 longitude degree is 111319.46 m 111319

Analysis 3

Working with cost/reverse_cost as time in seconds, x/y in lat/lon: Factor: would depend on the location of the points and on the average speed say 25m/s is the speed.

latitude conversion Factor
45 1 longitude degree is (78846.81m)/(25m/s) 3153 s
0 1 longitude degree is (111319.46 m)/(25m/s) 4452 s

History

• Functionality added version 2.3.0
• Renamed in version 2.0.0

## Deprecated Signature¶

Example: Using the deprecated signature
SELECT * FROM pgr_astar(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, 12, true, true);
NOTICE:  Deprecated signature of function pgr_astar
seq | id1 | id2 | cost
-----+-----+-----+------
0 |   2 |   4 |    1
1 |   5 |   8 |    1
2 |   6 |   9 |    1
3 |   9 |  15 |    1
4 |  12 |  -1 |    0
(5 rows)


The queries use the Sample Data network.