pgRouting Manual (2.3)

pgr_aStar

«  pgr_johnson   ::   Contents   ::   pgr_bdAstar - Bi-directional A* Shortest Path  »


pgr_aStar

Name

pgr_aStar — Returns the shortest path using A* algorithm.

../../../_images/boost-inside2.jpeg

Boost Graph Inside

Synopsis

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.

Characteristics

The main Characteristics are:

  • Process is done only on edges with positive costs.
  • Vertices of the graph are:
    • positive when it belongs to the edges_sql
    • negative when it belongs to the points_sql
  • Values are returned when there is a path.
    • When the starting vertex and ending vertex are the same, there is no path.
      • The agg_cost the non included values (v, v) is 0
    • When the starting vertex and ending vertex are the different and there is no path:
      • The agg_cost the non included values (u, v) is ∞
  • 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)\)

Signature Summary

pgr_aStar(edges_sql, start_vid, end_vid)
pgr_aStar(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)

Note

This signature is deprecated

pgr_aStar(sql, source integer, target integer, directed boolean, has_rcost boolean)
RETURNS SET OF pgr_costResult

Signatures

Minimal Signature

pgr_aStar(edges_sql, start_vid, end_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
Example:Using the defaults
SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

Complete Signature

pgr_aStar(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
Example:Setting a Heuristic
SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12, heuristic := 1);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12, heuristic := 2);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

Description of the Signatures

Note

The following only aplies to the new signature(s)

Description of the edges_sql query

edges_sql:an SQL query, which should return a set of rows with the following columns:
Column Type Default Description
id ANY-INTEGER   Identifier of the edge.
source ANY-INTEGER   Identifier of the first end point vertex of the edge.
target ANY-INTEGER   Identifier of the second end point vertex of the edge.
cost ANY-NUMERICAL  
Weight of the edge (source, target)
  • When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost ANY-NUMERICAL -1
Weight of the edge (target, source),
  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.
x1 ANY-NUMERICAL   X coordinate of source vertex.
y1 ANY-NUMERICAL   Y coordinate of source vertex.
x2 ANY-NUMERICAL   X coordinate of target vertex.
y2 ANY-NUMERICAL   Y coordinate of target vertex.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Description of the parameters of the signatures

Parameter Type Description
edges_sql TEXT Edges SQL query as described above.
start_vid ANY-INTEGER Starting vertex identifier.
end_vid ANY-INTEGER Ending vertex identifier.
directed BOOLEAN
  • Optional.
    • When false the graph is considered as Undirected.
    • Default is true which considers the graph as Directed.
heuristic INTEGER

(optional). Heuristic number. Current valid values 0~5. Default 5

  • 0: h(v) = 0 (Use this value to compare with pgr_dijkstra)
  • 1: h(v) abs(max(dx, dy))
  • 2: h(v) abs(min(dx, dy))
  • 3: h(v) = dx * dx + dy * dy
  • 4: h(v) = sqrt(dx * dx + dy * dy)
  • 5: h(v) = abs(dx) + abs(dy)
factor FLOAT (optional). For units manipulation. \(factor > 0\). Default 1.
epsilon FLOAT (optional). For less restricted results. \(factor >= 1\). Default 1.

Description of the return values

Returns set of (seq, path_seq, node, edge, cost, agg_cost)

Column Type Description
seq INTEGER Row sequence.
path_seq INTEGER Path sequence that indicates the relative position on the path.
node BIGINT
Identifier of the node:
  • A positive value indicates the node is a vertex of edges_sql.
  • A negative value indicates the node is a point of points_sql.
edge BIGINT
Identifier of the edge used to go from node to the next node in the path sequence.
  • -1 for the last row in the path sequence.
cost FLOAT
Cost to traverse from node using edge to the next node in the path sequence.
  • 0 for the last row in the path sequence.
agg_cost FLOAT
Aggregate cost from start_vid to node.
  • 0 for the first row in the path sequence.

About 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

History

  • Functionality added version 2.3.0
  • Renamed in version 2.0.0

Deprecated Signature

Example:Using the deprecated signature
SELECT * FROM pgr_astar(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12, true, true);
NOTICE:  Deprecated signature of function pgr_astar
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |   8 |    1
   2 |   6 |   9 |    1
   3 |   9 |  15 |    1
   4 |  12 |  -1 |    0
(5 rows)

The queries use the Sample Data network.

«  pgr_johnson   ::   Contents   ::   pgr_bdAstar - Bi-directional A* Shortest Path  »