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

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

Description¶

The main Characteristics are:

Process works for directed and undirected graphs.
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$
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)$

aStar optional Parameters¶

Parameter	Type	Default	Description
`heuristic`	`INTEGER`	5	Heuristic number. Current valid values 0~5. 0: $h (v) = 0$ (Use this value to compare with pgr_dijkstra) 1: $h (v) = a b s (m a x (Δ x, Δ y))$ 2: $h (v) = a b s (m i n (Δ x, Δ y))$ 3: $h (v) = Δ x * Δ x + Δ y * Δ y$ 4: $h (v) = s q r t (Δ x * Δ x + Δ y * Δ y)$ 5: $h (v) = a b s (Δ x) + a b s (Δ y)$
`factor`	`FLOAT`	`1`	For units manipulation. $f a c t o r > 0$ .
`epsilon`	`FLOAT`	`1`	For less restricted results. $e p s i l o n >= 1$ .

Parameter

Type

Default

Description

heuristic

INTEGER

Heuristic number. Current valid values 0~5.

0: $h (v) = 0$ (Use this value to compare with pgr_dijkstra)
1: $h (v) = a b s (m a x (Δ x, Δ y))$
2: $h (v) = a b s (m i n (Δ x, Δ y))$
3: $h (v) = Δ x * Δ x + Δ y * Δ y$
4: $h (v) = s q r t (Δ x * Δ x + Δ y * Δ y)$
5: $h (v) = a b s (Δ x) + a b s (Δ y)$

factor

FLOAT

1

For units manipulation. $f a c t o r > 0$ .

epsilon

FLOAT

1

For less restricted results. $e p s i l o n >= 1$ .

See heuristics available and factor handling.

Advanced documentation¶

Heuristic¶

Currently the heuristic functions available are:

0: $h (v) = 0$ (Use this value to compare with pgr_dijkstra)
1: $h (v) = a b s (m a x (Δ x, Δ y))$
2: $h (v) = a b s (m i n (Δ x, Δ y))$
3: $h (v) = Δ x * Δ x + Δ y * Δ y$
4: $h (v) = s q r t (Δ x * Δ x + Δ y * Δ y)$
5: $h (v) = a b s (Δ x) + a b s (Δ y)$

where $Δ x = x_{1} - x_{0}$ and $Δ 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