Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5 2.4

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.

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 $\mathrm{\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)\ast \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)\ast \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(\mathrm{\Delta }x,\mathrm{\Delta }y))$

• 2: $h(v)=abs(min(\mathrm{\Delta }x,\mathrm{\Delta }y))$

• 3: $h(v)=\mathrm{\Delta }x\ast \mathrm{\Delta }x+\mathrm{\Delta }y\ast \mathrm{\Delta }y$

• 4: $h(v)=sqrt(\mathrm{\Delta }x\ast \mathrm{\Delta }x+\mathrm{\Delta }y\ast \mathrm{\Delta }y)$

• 5: $h(v)=abs(\mathrm{\Delta }x)+abs(\mathrm{\Delta }y)$

where $\mathrm{\Delta }x=x_1-x_0$ and $\mathrm{\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