pgr_aStar¶
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 subset 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  ANYINTEGER  Identifier of the edge.  
source  ANYINTEGER  Identifier of the first end point vertex of the edge.  
target  ANYINTEGER  Identifier of the second end point vertex of the edge.  
cost  ANYNUMERICAL 


reverse_cost  ANYNUMERICAL  1 

x1  ANYNUMERICAL  X coordinate of source vertex.  
y1  ANYNUMERICAL  Y coordinate of source vertex.  
x2  ANYNUMERICAL  X coordinate of target vertex.  
y2  ANYNUMERICAL  Y coordinate of target vertex. 
Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 

ANYNUMERICAL:  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  ANYINTEGER  Starting vertex identifier. 
end_vid  ANYINTEGER  Ending vertex identifier. 
directed  BOOLEAN 

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

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 

edge  BIGINT 

cost  FLOAT 

agg_cost  FLOAT 

About factor¶
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.