# pgRouting Manual (3.6)

## pgr_dijkstraCostMatrix

# `pgr_dijkstraCostMatrix`

`pgr_dijkstraCostMatrix` - Calculates a cost matrix using pgr_dijkstra.

Boost Graph Inside

Availability

- Version 3.0.0

  - Official function

- Version 2.3.0

  - New proposed function

## Description

Using Dijkstra algorithm, calculate and return a cost matrix.

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.

The main Characteristics are:

- Can be used as input to pgr_TSP.

  - Use directly when the resulting matrix is symmetric and there is no \(\infty\) value.

  - It will be the users responsibility to make the matrix symmetric.

    - By using geometric or harmonic average of the non symmetric values.

    - By using max or min the non symmetric values.

    - By setting the upper triangle to be the mirror image of the lower triangle.

    - By setting the lower triangle to be the mirror image of the upper triangle.

  - It is also the users responsibility to fix an \(\infty\) value.

- Each function works as part of the family it belongs to.

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

  - When the starting vertex and ending vertex are the same, there is no path.

    - The aggregate cost in the non included values (v, v) is 0.

  - When the starting vertex and ending vertex are the different and there is no path.

    - The aggregate cost in the non included values (u, v) is \(\infty\).

- Let be the case the values returned are stored in a table:

  - The unique index would be the pair: `(start_vid, end_vid)`.

- Depending on the function and its parameters, the results can be symmetric.

  - The aggregate cost of (u, v) is the same as for (v, u).

- Any duplicated value in the start vids are ignored.

- The returned values are ordered:

  - `start_vid` ascending

  - `end_vid` ascending

## Signatures

Summary

pgr_dijkstraCostMatrix(Edges SQL, start vids, [`directed`])

Returns set of `(start_vid, end_vid, agg_cost)`
OR EMPTY SET

Example:

  Symmetric cost matrix for vertices \(\{5, 6, 10, 15\}\) on an undirected graph

    SELECT * FROM pgr_dijkstraCostMatrix(
      'SELECT id, source, target, cost, reverse_cost FROM edges',
      (SELECT array_agg(id)
        FROM vertices
        WHERE id IN (5, 6, 10, 15)),
      false);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             5 |       6 |        1
             5 |      10 |        2
             5 |      15 |        3
             6 |       5 |        1
             6 |      10 |        1
             6 |      15 |        2
            10 |       5 |        2
            10 |       6 |        1
            10 |      15 |        1
            15 |       5 |        3
            15 |       6 |        2
            15 |      10 |        1
    (12 rows)

## Parameters

Column | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below
start vids | `ARRAY[BIGINT]` | Array of identifiers of starting vertices.

### Optional parameters

Column | Type | Default | Description
--- | --- | --- | ---

`directed`

`BOOLEAN`

`true`

- When `true` the graph is considered Directed

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

## Inner Queries

### Edges SQL

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

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

## Result columns

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

## Additional Examples

Example:

  Use with pgr_TSP.

    SELECT * FROM pgr_TSP(
      $$
      SELECT * FROM pgr_dijkstraCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edges',
        (SELECT array_agg(id)
          FROM vertices
          WHERE id IN (5, 6, 10, 15)),
        false)
      $$);
    NOTICE:  pgr_TSP no longer solving with simulated annaeling
    HINT:  Ignoring annaeling parameters
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |    5 |    0 |        0
       2 |    6 |    1 |        1
       3 |   10 |    1 |        2
       4 |   15 |    1 |        3
       5 |    5 |    3 |        6
    (5 rows)

## See Also

- Dijkstra - Family of functions

- Cost Matrix - Category

- Traveling Sales Person - Family of functions

- Sample Data

Indices and tables

- Index

- Search Page