Name¶

pgr_aStar — Returns the shortest path using A* algorithm.

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)

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

Signatures¶

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

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)

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

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¶

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:

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.

History

• Functionality added version 2.3.0
• Renamed in version 2.0.0

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.

See Also¶

• http://www.boost.org/libs/graph/doc/astar_search.html
• http://en.wikipedia.org/wiki/A*_search_algorithm