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
- first by
- 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\)
- If there is no path from \(v\) to \(u\):
- 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.
|
factor |
FLOAT |
1 |
For units manipulation. \(factor > 0\). |
epsilon |
FLOAT |
1 |
For less restricted results. \(epsilon >= 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) = 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 |