A* - 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.

Description

The main Characteristics are:

  • Process works for directed and undirected graphs.

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

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

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

factor

FLOAT

1

For units manipulation. \(factor > 0\) .

epsilon

FLOAT

1

For less restricted results. \(epsilon >= 1\) .

See heuristics available and factor handling.

Advanced documentation

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

See Also

Indices and tables