## pgr_dijkstraNearCost - Proposed

``` pgr_dijkstraNearCost ``` - Using dijkstra algorithm, finds the route that leads to the nearest vertex.

Warning

Proposed functions for next mayor release.

• They are not officially in the current release.

• They will likely officially be part of the next mayor release:

• The functions make use of ANY-INTEGER and ANY-NUMERICAL

• Name might not change. (But still can)

• Signature might not change. (But still can)

• Functionality might not change. (But still can)

• pgTap tests have being done. But might need more.

• Documentation might need refinement.

Availability

• Version 3.3.0

• Promoted to proposed function

• Version 3.2.0

• New experimental function

### Description

Given a graph, a starting vertex and a set of ending vertices, this function finds the shortest path from the starting vertex to the nearest ending vertex.

#### Characteristics

• Uses Dijkstra algorithm.

• Works for directed and undirected graphs.

• When there are more than one path to the same vertex with same cost:

• The algorithm will return just one path

• Optionally allows to find more than one path.

• When more than one path is to be returned:

• Results are sorted in increasing order of:

• aggregate cost

• Within the same value of aggregate costs:

• results are sorted by (source, target)

• Running time: Dijkstra running time: \(drt = O((E + V)logV)\)

• One to Many; \(drt\)

• Many to One: \(drt\)

• Many to Many: \(drt * Starting vids\)

• Combinations: \(drt * Starting vids\)

### Signatures

Summary

```pgr_dijkstraNearCost(Edges SQL, Start vid,  End vids  [, directed] [, cap])
pgr_dijkstraNearCost(Edges SQL, Start vids, End vid   [, directed] [, cap])
pgr_dijkstraNearCost(Edges SQL, Start vids, End vids  [, directed] [, cap], [global])
pgr_dijkstraNearCost(Edges SQL, Combinations SQL  [, directed] [, cap], [global])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
```

#### One to Many

```pgr_dijkstraNearCost(Edges SQL, Start vid,  End vids [, directed] [, cap])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
```
Example :

Departing on car from vertex \(2\) find the nearest subway station.

• Using a directed graph for car routing.

• The subway stations are on the following vertices \(\{ 3, 6, 7\}\)

• The defaults used:

• directed => true

• cap => 1

```1SELECT * FROM pgr_dijkstraNearCost(
2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3    2, ARRAY[3, 6, 7]
4);
5 start_vid  end_vid  agg_cost
6-----------+---------+----------
7         2        6         2
8(1 row)
9
```

The result shows that station at vertex \(6\) is the nearest.

#### Many to One

```pgr_dijkstraNearCost(Edges SQL, Start vids, End vid  [, directed] [, cap])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
```
Example :

Departing on a car from a subway station find the nearest two stations to vertex \(2\)

• Using a directed graph for car routing.

• The subway stations are on the following vertices \(\{ 3, 6, 7\}\)

• On line 4 : using the positional parameter: directed set to ``` true ```

• In line 5 : using named parameter cap => 2

``` 1SELECT * FROM pgr_dijkstraNearCost(
2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3    ARRAY[3, 6, 7], 2,
4    true,
5    cap => 2
6);
7 start_vid  end_vid  agg_cost
8-----------+---------+----------
9         3        2         1
10         6        2         2
11(2 rows)
12
```

The result shows that station at vertex \(3\) is the nearest and the next best is \(6\) .

#### Many to Many

```pgr_dijkstraNearCost(Edges SQL, Start vids, End vids [, directed] [, cap], [global])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
```
Example :

Find the best pedestrian connection between two lines of buses

• Unsing an undirected graph for pedestrian routing

• The first subway line stations stops are at \(\{3, 6, 7\}\)

• The second subway line stations are at \(\{4, 9\}\)

• On line 4 : using the named parameter: directed => false

• The defaults used:

• cap => 1

• global => true

``` 1SELECT * FROM pgr_dijkstraNearCost(
2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3    ARRAY[4, 9], ARRAY[3, 6, 7],
4    directed => false
5);
6 start_vid  end_vid  agg_cost
7-----------+---------+----------
8         4        3         1
9(1 row)
10
```

For a pedestrian the best connection is to get on/off is at vertex \(3\) of the first subway line and at vertex \(4\) of the second subway line.

Only one route is returned because global is ``` true ``` and cap is ``` 1 ```

#### Combinations

```pgr_dijkstraNearCost(Edges SQL, Combinations SQL  [, directed] [, cap], [global])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
```
Example :

Find the best car connection between all the stations of two subway lines

• Using a directed graph for car routing.

• The first subway line stations stops are at \(\{3, 6, 7\}\)

• The second subway line stations are at \(\{4, 9\}\)

• line 3 sets the start vertices to be from the fisrt subway line and the ending vertices to be from the second subway line

• line 5 sets the start vertices to be from the first subway line and the ending vertices to be from the first subway line

• On line 6 : using the named parameter is global => false

• The defaults used:

• directed => true

• cap => 1

``` 1SELECT * FROM pgr_dijkstraNearCost(
2    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
3    'SELECT unnest(ARRAY[3, 6, 7]) as source, target FROM (SELECT unnest(ARRAY[4, 9]) AS target) a
4    UNION
5    SELECT unnest(ARRAY[4, 9]), target FROM (SELECT unnest(ARRAY[3, 6, 7]) AS target) b',
6    global => false
7);
8 start_vid  end_vid  agg_cost
9-----------+---------+----------
10         4        3         1
11         6        9         1
12         9        6         1
13         3        9         2
14         7        9         4
15(5 rows)
16
```

From the results:

• making a connection from the first subway line to the second:

• \({(3 -> 9) (6 -> 9) (7 -> 9)}\) and the best one is \((6 -> 9)\) with a cost of \(1\) (line: 11 )

• making a connection from the second subway line to the first:

• \({(4 -> 3) (9 -> 6)}\) and both are equaly good as they have the same cost. (lines: 10 and 12 )

### Parameters

Parameter

Type

Default

Description

Edges SQL

``` TEXT ```

Edges query as described below

Combinations SQL

``` TEXT ```

Combinations query 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.

directed

``` BOOLEAN ```

``` true ```

• When ``` true ``` the graph is considered Directed

• When ``` false ``` the graph is considered as Undirected .

cap

``` BIGINT ```

1

Find at most ``` cap ``` number of nearest shortest paths

global

``` BOOLEAN ```

``` true ```

• When ``` true ``` : only ``` cap ``` limit results will be returned

• When ``` false ``` : ``` cap ``` limit per ``` Start vid ``` will be returned

### Inner query

#### Edges query

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.

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.

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

### Return Columns

Returns SET OF ``` (start_vid, end_vid, agg_cost) ```

Column

Type

Description

start_vid

``` BIGINT ```

Identifier of the starting vertex.

end_vid

``` BIGINT ```

Identifier of the ending vertex.

agg_cost

``` FLOAT ```

Aggregate cost from ``` start_vid ``` to ``` end_vid ``` .