aStar  Family of functions  pgRouting Manual (3.3)
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)\)
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