aStar  Family of functions¶
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.
pgr_aStar  A* algorithm for the shortest path.
pgr_aStarCost  Get the aggregate cost of the shortest paths.
pgr_aStarCostMatrix  Get the cost matrix of the shortest paths.
General Information¶
The main Characteristics are:
Default kind of graph is directed when
directed
flag is missing.directed
flag is set to true
Unless specified otherwise, ordering is:
first by
start_vid
(if exists)then by
end_vid
Values are returned when there is a path
Let \(v\) and \(u\) be nodes on the graph:
If there is no path from \(v\) to \(u\):
no corresponding row is returned
agg_cost
from \(v\) to \(u\) is \(\infty\)
There is no path when \(v = u\) therefore
no corresponding row is returned
agg_cost
from v to u is \(0\)
Edges with negative costs are not included in the graph.
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)\)
Parameters¶
Column 
Type 
Description 


Edges SQL as described below 


Combinations SQL as described below 

start vid 

Identifier of the starting vertex of the path. 
start vids 

Array of identifiers of starting vertices. 
end vid 

Identifier of the ending vertex of the path. 
end vids 

Array of identifiers of ending vertices. 
Optional parameters¶
Column 
Type 
default 
Description 





aStar optional Parameters¶
Parameter 
Type 
Default 
Description 


INTEGER 
5 
Heuristic number. Current valid values 0~5.




For units manipulation. \(factor > 0\). See Factor 



For less restricted results. \(epsilon >= 1\). 
Inner queries¶
Edges SQL¶
Parameter 
Type 
Default 
Description 


ANYINTEGER 
Identifier of the edge. 


ANYINTEGER 
Identifier of the first end point vertex of the edge. 


ANYINTEGER 
Identifier of the second end point vertex of the edge. 


ANYNUMERICAL 
Weight of the edge (



ANYNUMERICAL 
1 
Weight of the edge (


ANYNUMERICAL 
X coordinate of 


ANYNUMERICAL 
Y coordinate of 


ANYNUMERICAL 
X coordinate of 


ANYNUMERICAL 
Y coordinate of 
Where:
 ANYINTEGER
SMALLINT
,INTEGER
,BIGINT
 ANYNUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Combinations SQL¶
Parameter 
Type 
Description 


ANYINTEGER 
Identifier of the departure vertex. 

ANYINTEGER 
Identifier of the arrival vertex. 
Where:
 ANYINTEGER
SMALLINT
,INTEGER
,BIGINT
Advanced documentation¶
The A* (pronounced “A Star”) algorithm is based on Dijkstra’s algorithm with a heuristic, that is an estimation of the remaining cost from the vertex to the goal, that allows to solve most shortest path problems by evaluation only a subset of the overall graph.
Running time: \(O((E + V) * \log V)\)
Heuristic¶
Currently the heuristic functions available are:
0: \(h(v) = 0\) (Use this value to compare with pgr_dijkstra)
1: \(h(v) = abs(max(\Delta x, \Delta y))\)
2: \(h(v) = abs(min(\Delta x, \Delta y))\)
3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\)
4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\)
5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)
where \(\Delta x = x_1  x_0\) and \(\Delta y = y_1  y_0\)
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 
See Also¶
Indices and tables