Supported versions: Latest (3.3) 3.2 3.1 3.0
Unsupported versions: 2.6 2.5 2.4

aStar - 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.

General Information¶

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)\)

Parameters¶

Column	Type	Description
Edges SQL	`TEXT`	Edges SQL as described below
Combinations SQL	`TEXT`	Combinations SQL as described below
start vid	`BIGINT`	Identifier of the starting vertex of the path.
start vids	`ARRAY[BIGINT]`	Array of identifiers of starting vertices.
end vid	`BIGINT`	Identifier of the ending vertex of the path.
end vids	`ARRAY[BIGINT]`	Array of identifiers of ending vertices.

Optional parameters¶

Column	Type	default	Description
`directed`	`BOOLEAN`	`true`	When `true` the graph is considered Directed When `false` the graph is considered as Undirected.

aStar optional Parameters¶

Parameter	Type	Default	Description
`heuristic`	INTEGER	5	Heuristic number. Current valid values 0~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\).

Parameter

Type

Default

Description

heuristic

INTEGER

Heuristic number. Current valid values 0~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 SQL¶

Parameter	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 SQL¶

Parameter	Type	Description
`source`	ANY-INTEGER	Identifier of the departure vertex.
`target`	ANY-INTEGER	Identifier of the arrival vertex.

Where:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT

Advanced documentation¶

The A* (pronounced “A Star”) algorithm is based on Dijkstra’s algorithm with a heuristic, that is an estimation of the remaining cost from the vertex to the goal, that allows to solve most shortest path problems by evaluation only a sub-set of the overall graph.

Running time: \(O((E + V) * \log V)\)

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