pgr_astar - Shortest Path A*¶

Name¶

pgr_astar — Returns the shortest path using A* algorithm.

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. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.

pgr_costResult[] pgr_astar(sql text, source integer, target integer,
                       directed boolean, has_rcost boolean);

Description¶

sql:

a SQL query, which should return a set of rows with the following columns:

SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table

id:	`int4` identifier of the edge
source:	`int4` identifier of the source vertex
target:	`int4` identifier of the target vertex
cost:	`float8` value, of the edge traversal cost. A negative cost will prevent the edge from being inserted in the graph.
x1:	`x` coordinate of the start point of the edge
y1:	`y` coordinate of the start point of the edge
x2:	`x` coordinate of the end point of the edge
y2:	`y` coordinate of the end point of the edge
reverse_cost:	(optional) the cost for the reverse traversal of the edge. This is only used when the `directed` and `has_rcost` parameters are `true` (see the above remark about negative costs).

source:

int4 id of the start point

target:

int4 id of the end point

directed:

true if the graph is directed

has_rcost:

if true, the reverse_cost column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

Returns set of pgr_costResult[]:

seq:	row sequence
id1:	node ID
id2:	edge ID (`-1` for the last row)
cost:	cost to traverse from `id1` using `id2`

History

Renamed in version 2.0.0

Examples¶

Without reverse_cost

SELECT * FROM pgr_AStar(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2 FROM edge_table',
    4, 1, false, false);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   4 |  16 |    1
   1 |   9 |   9 |    1
   2 |   6 |   8 |    1
   3 |   5 |   4 |    1
   4 |   2 |   1 |    1
   5 |   1 |  -1 |    0
(6 rows)

With reverse_cost

SELECT * FROM pgr_AStar(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost FROM edge_table ',
    4, 1, true, true);
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   4 |   3 |    1
   1 |   3 |   2 |    1
   2 |   2 |   1 |    1
   3 |   1 |  -1 |    0
(4 rows)

The queries use the Sample Data network.

pgRouting Manual (2.2)