# pgRouting Manual (3.3)

## pgr_dijkstraNearCost - Proposed

- Supported versions: Latest (3.3) 3.2

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

Boost Graph Inside

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

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

## See Also

- Dijkstra - Family of functions

- pgr_dijkstraNear - Proposed

- Sample Data network.

- boost: https://www.boost.org/libs/graph/doc/table_of_contents.html

- Wikipedia: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Indices and tables

- Index

- Search Page