Navigation :

Table of Contents - pgRouting Manual (3.2) > pgr_aStar - pgRouting Manual (3.2)

pgr_aStar - pgRouting Manual (3.2)

Supported versions: Latest ( 3.2 ) 3.1 3.0
Unsupported versions: 2.6 2.5 2.4 2.3 2.2 2.1 2.0

pgr_aStar

pgr_aStar - Shortest path using A* algorithm.

images/boost-inside.jpeg — Boost Graph Inside

Availability

Version 3.2.0
- New proposed function:
  - pgr_aStar(Combinations)
Version 3.0.0
- Official function
Version 2.4.0
- New Proposed functions:
  - pgr_aStar(One to Many)
  - pgr_aStar(Many to One)
  - pgr_aStar(Many to Many)
Version 2.3.0
- Signature change on pgr_astar(One to One)
  - Old signature no longer supported
Version 2.0.0
- Official pgr_aStar(One to One)

Description

The main characteristics are:

Default kind of graph is directed when
- directed flag is missing.
- directed flag is set to true
Unless specified otherwise, 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\)
Edges with negative costs are not included in the graph.
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)\)

The results are equivalent to the union of the results of the pgr_aStar( One to One ) on the:
- pgr_aStar( One to Many )
- pgr_aStar( Many to One )
- pgr_aStar( Many to Many )
start_vid and end_vid in the result is used to distinguish to which path it belongs.

Signatures

Summary

     pgr_aStar(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon]) -- Proposed on v3.2

RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET

    

Optional parameters are named parameters and have a default value.

Using defaults

     pgr_aStar(Edges SQL, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

    

Example :: From vertex \(2\) to vertex \(12\) on a directed graph

     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    11     1         2
   4         4    11    13     1         3
   5         5    12    -1     0         4
(5 rows)


    

One to One

      pgr_aStar(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])

RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Example :: From vertex \(2\) to vertex \(12\) on an undirected graph using heuristic \(2\)

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


     

One to many

      pgr_aStar(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

     

Example :: From vertex \(2\) to vertices \(\{3, 12\}\) on a directed graph using heuristic \(2\)

      SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, ARRAY[3, 12], heuristic := 2);
 seq  path_seq  end_vid  node  edge  cost  agg_cost
-----+----------+---------+------+------+------+----------
   1         1        3     2     4     1         0
   2         2        3     5     8     1         1
   3         3        3     6     9     1         2
   4         4        3     9    16     1         3
   5         5        3     4     3     1         4
   6         6        3     3    -1     0         5
   7         1       12     2     4     1         0
   8         2       12     5    10     1         1
   9         3       12    10    12     1         2
  10         4       12    11    13     1         3
  11         5       12    12    -1     0         4
(11 rows)


     

Many to One

      pgr_aStar(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

     

Example :: From vertices \(\{7, 2\}\) to vertex \(12\) on a directed graph using heuristic \(0\)

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


     

Many to Many

      pgr_aStar(Edges SQL, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

     

Example :: From vertices \(\{7, 2\}\) to vertices \(\{3, 12\}\) on a directed graph using heuristic \(2\)

      SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    ARRAY[7, 2], ARRAY[3, 12], heuristic := 2);
 seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
       1          2        3     2     4     1         0
       2          2        3     5     8     1         1
       3          2        3     6     9     1         2
       4          2        3     9    16     1         3
       5          2        3     4     3     1         4
       6          2        3     3    -1     0         5
       1          2       12     2     4     1         0
       2          2       12     5    10     1         1
       3          2       12    10    12     1         2
       4          2       12    11    13     1         3
       5          2       12    12    -1     0         4
       1          7        3     7     6     1         0
       2          7        3     8     7     1         1
       3          7        3     5     8     1         2
       4          7        3     6     9     1         3
       5          7        3     9    16     1         4
       6          7        3     4     3     1         5
       7          7        3     3    -1     0         6
       1          7       12     7     6     1         0
       2          7       12     8     7     1         1
       3          7       12     5    10     1         2
       4          7       12    10    12     1         3
       5          7       12    11    13     1         4
       6          7       12    12    -1     0         5
(24 rows)


     

Combinations

      pgr_aStar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

     

Example :: Using a combinations table on a directed graph using heuristic \(2\) .

      SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    'SELECT * FROM ( VALUES (7, 3), (2, 12) ) AS t(source, target)',
    heuristic := 2);
 seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1         1          2       12     2     4     1         0
   2         2          2       12     5    10     1         1
   3         3          2       12    10    12     1         2
   4         4          2       12    11    13     1         3
   5         5          2       12    12    -1     0         4
   6         1          7        3     7     6     1         0
   7         2          7        3     8     7     1         1
   8         3          7        3     5     8     1         2
   9         4          7        3     6     9     1         3
  10         5          7        3     9    16     1         4
  11         6          7        3     4     3     1         5
  12         7          7        3     3    -1     0         6
(12 rows)


     

Parameters

Parameter	Type	Description
Edges SQL	`TEXT`	Edges query as described below.
Combinations SQL	`TEXT`	Combinations query as described below.
from_vid	`ANY-INTEGER`	Starting vertex identifier. Parameter in: One to One One to Many
from_vids	`ARRAY[ANY-INTEGER]`	Array of starting vertices identifiers. Parameter in: Many to One Many to Many
to_vid	`ANY-INTEGER`	Ending vertex identifier. Parameter in: One to One Many to One
to_vids	`ARRAY[ANY-INTEGER]`	Array of ending vertices identifiers. Parameter in: One to Many Many to Many

Optional Parameters

Parameter	Type	Default	Description
directed	`BOOLEAN`	`true`	When `true` the graph is considered as Directed. When `false` the graph is considered as Undirected.
heuristic	`INTEGER`	`5`	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`	`1`	For units manipulation. \(factor > 0\) . See Factor
epsilon	`FLOAT`	`1`	For less restricted results. \(epsilon >= 1\) .

Inner queries

Edges 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

Combinations query

Column	Type	Default	Description
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.