# 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 sub-set of the overall graph.

• Supported versions: current(3.0) 2.6
• Unsupported versions: 2.5 2.4

## 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)$$

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