# pgRouting Manual (3.1)

## 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.

- 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.

Previous versions of this page

- Supported versions: current(3.1) 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)\)

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

## See Also

- pgr_aStar

- pgr_aStarCost

- pgr_aStarCostMatrix

- https://www.boost.org/libs/graph/doc/astar_search.html

- https://en.wikipedia.org/wiki/A*_search_algorithm

Indices and tables

- Index

- Search Page