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

#### 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