# pgRouting Manual (2.5)

## pgr_dijkstraCost

## Synopsis

`pgr_dijkstraCost`

Using Dijkstra algorithm implemented by Boost.Graph, and extract only the aggregate cost of the shortest path(s) found, for the combination of vertices given.

Boost Graph Inside

Availability

- pgr_dijkstraCost(all signatures) 2.2.0

The `pgr_dijkstraCost` algorithm, is a good choice to calculate the sum of the costs of the shortest path for a subset of pairs of nodes of the graph. We make use of the Boost’s implementation of dijkstra which runs in \(O(V \log V + E)\) time.

## Characteristics

The main Characteristics are:
  - It does not return a path.
  - Returns the sum of the costs of the shortest path for pair combination of nodes in the graph.
  - Process is done only on edges with positive costs.
  - Values are returned when there is a path.
    - The returned values are in the form of a set of (start_vid, end_vid, agg_cost).
    - When the starting vertex and ending vertex are the same, there is no path.
      - The agg_cost int the non included values (v, v) is 0
    - When the starting vertex and ending vertex are the different and there is no path.
      - The agg_cost in the non included values (u, v) is \(\infty\)
  - Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid).
  - For undirected graphs, the results are symmetric.
    - The agg_cost of (u, v) is the same as for (v, u).
  - Any duplicated value in the start_vids or end_vids is ignored.
  - The returned values are ordered:
    - start_vid ascending
    - end_vid ascending
  - Running time: \(O(| start\_vids | * (V \log V + E))\)

## Signature Summary

    pgr_dijkstraCost(edges_sql, start_vid, end_vid);
    pgr_dijkstraCost(edges_sql, start_vid, end_vid, directed);
    pgr_dijkstraCost(edges_sql, start_vids, end_vid, directed);
    pgr_dijkstraCost(edges_sql, start_vid, end_vids, directed);
    pgr_dijkstraCost(edges_sql, start_vids, end_vids, directed);

        RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET

## Signatures

### Minimal signature

The minimal signature is for a directed graph from one `start_vid` to one `end_vid`:

    pgr_dijkstraCost(TEXT edges_sql, BIGINT start_vid, BIGINT end_vid)
        RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET

Example

    SELECT * FROM pgr_dijkstraCost(
        'select id, source, target, cost, reverse_cost from edge_table',
        2, 3);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             2 |       3 |        5
    (1 row)

### pgr_dijkstraCost One to One

This signature performs a Dijkstra from one `start_vid` to one `end_vid`:
  - on a directed graph when `directed` flag is missing or is set to `true`.
  - on an undirected graph when `directed` flag is set to `false`.

    pgr_dijkstraCost(TEXT edges_sql, BIGINT start_vid, BIGINT end_vid,
                         BOOLEAN directed:=true);
        RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET

Example: |

    SELECT * FROM pgr_dijkstraCost(
        'select id, source, target, cost, reverse_cost from edge_table',
        2, 3, false);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             2 |       3 |        1
    (1 row)

### pgr_dijkstraCost One to Many

    pgr_dijkstraCost(TEXT edges_sql, BIGINT start_vid, array[ANY_INTEGER] end_vids,
            BOOLEAN directed:=true);
        RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET

This signature performs a Dijkstra from one `start_vid` to each `end_vid` in `end_vids`:
  - on a directed graph when `directed` flag is missing or is set to `true`.
  - on an undirected graph when `directed` flag is set to `false`.

Example: |

    SELECT * FROM pgr_dijkstraCost(
        'select id, source, target, cost, reverse_cost from edge_table',
        2, ARRAY[3, 11]);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             2 |       3 |        5
             2 |      11 |        3
    (2 rows)

### pgr_dijkstraCost Many to One

    pgr_dijkstraCost(TEXT edges_sql, array[ANY_INTEGER] start_vids, BIGINT end_vid,
                         BOOLEAN directed:=true);
        RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET

This signature performs a Dijkstra from each `start_vid` in `start_vids` to one `end_vid`:
  - on a directed graph when `directed` flag is missing or is set to `true`.
  - on an undirected graph when `directed` flag is set to `false`.

Example: |

    SELECT * FROM pgr_dijkstraCost(
        'select id, source, target, cost, reverse_cost from edge_table',
        ARRAY[2, 7], 3);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             2 |       3 |        5
             7 |       3 |        6
    (2 rows)

### pgr_dijkstraCost Many to Many

    pgr_dijkstraCost(TEXT edges_sql, array[ANY_INTEGER] start_vids, array[ANY_INTEGER] end_vids,
            BOOLEAN directed:=true);
        RETURNS SET OF (start_vid, end_vid, agg_cost) or EMPTY SET

This signature performs a Dijkstra from each `start_vid` in `start_vids` to each `end_vid` in `end_vids`:
  - on a directed graph when `directed` flag is missing or is set to `true`.
  - on an undirected graph when `directed` flag is set to `false`.

Example: |

    SELECT * FROM pgr_dijkstraCost(
        'select id, source, target, cost, reverse_cost from edge_table',
        ARRAY[2, 7], ARRAY[3, 11]);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             2 |       3 |        5
             2 |      11 |        3
             7 |       3 |        6
             7 |      11 |        4
    (4 rows)

## Description of the Signatures

### Description of the edges_sql query for dijkstra like functions

edges_sql: | an SQL query, which should return a set of rows with the following columns:

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

### Description of the parameters of the signatures

Column | Type | Default | Description
--- | --- | --- | ---
sql | `TEXT` |  | SQL query as described above.
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` Graph is considered Directed
- When `false` the graph is considered as Undirected.

### Description of the return values for a Cost function

Returns set of `(start_vid, end_vid, agg_cost)`

Column | Type | Description
--- | --- | ---
start_vid | `BIGINT` | Identifier of the starting vertex. Used when multiple starting vetrices are in the query.
end_vid | `BIGINT` | Identifier of the ending vertex. Used when multiple ending vertices are in the query.
agg_cost | `FLOAT` | Aggregate cost from `start_vid` to `end_vid`.

## Additional Examples

Example 1: | Demonstration of repeated values are ignored, and result is sorted.

    SELECT * FROM pgr_dijkstraCost(
            'select id, source, target, cost, reverse_cost from edge_table',
                ARRAY[5, 3, 4, 3, 3, 4], ARRAY[3, 5, 3, 4]);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             3 |       4 |        3
             3 |       5 |        2
             4 |       3 |        1
             4 |       5 |        3
             5 |       3 |        4
             5 |       4 |        3
    (6 rows)

Example 2: | Making start_vids the same as end_vids

    SELECT * FROM pgr_dijkstraCost(
            'select id, source, target, cost, reverse_cost from edge_table',
                ARRAY[5, 3, 4], ARRAY[5, 3, 4]);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             3 |       4 |        3
             3 |       5 |        2
             4 |       3 |        1
             4 |       5 |        3
             5 |       3 |        4
             5 |       4 |        3
    (6 rows)

## See Also

- http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- Sample Data network.

Indices and tables

- Index
- Search Page