# pgRouting Manual (3.3)

## pgr_bdDijkstraCostMatrix

- Supported versions: Latest (3.3) 3.2 3.1 3.0

- Unsupported versions: 2.6 2.5

# pgr_bdDijkstraCostMatrix

`pgr_bdDijkstraCostMatrix` - Calculates the a cost matrix using pgr_bdDijkstra.

Boost Graph Inside

Availability:

- Version 3.0.0

  - Official function

- Version 2.5.0

  - New proposed function

## Description

The main characteristics are:

- 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 agg_cost 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 the non included values (u, v) is \(\infty\)

- Running time (worse case scenario): \(O((V \log V + E))\)

- For large graphs where there is a path bewtween the starting vertex and ending vertex:

  - It is expected to terminate faster than pgr_dijkstra

- Returns a cost matrix.

## Signatures

Summary

    pgr_bdDijkstraCostMatrix(edges_sql, start_vids [, directed])
    RETURNS SET OF (start_vid, end_vid, agg_cost)

Using default

    pgr_bdDijkstraCostMatrix(edges_sql, start_vid)
    RETURNS SET OF (start_vid, end_vid, agg_cost)

Example

  Cost matrix for vertices \(\{1, 2, 3, 4\}\) on a directed graph

    SELECT * FROM pgr_bdDijkstraCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 5)
    );
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             1 |       2 |        1
             1 |       3 |        6
             1 |       4 |        5
             2 |       1 |        1
             2 |       3 |        5
             2 |       4 |        4
             3 |       1 |        2
             3 |       2 |        1
             3 |       4 |        3
             4 |       1 |        3
             4 |       2 |        2
             4 |       3 |        1
    (12 rows)

### Complete Signature

    pgr_bdDijkstraCostMatrix(edges_sql, start_vids [, directed])
    RETURNS SET OF (start_vid, end_vid, agg_cost)

Example

  Symmetric cost matrix for vertices \(\{1, 2, 3, 4\}\) on an undirected graph

    SELECT * FROM pgr_bdDijkstraCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 5),
        false
    );
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             1 |       2 |        1
             1 |       3 |        2
             1 |       4 |        3
             2 |       1 |        1
             2 |       3 |        1
             2 |       4 |        2
             3 |       1 |        2
             3 |       2 |        1
             3 |       4 |        1
             4 |       1 |        3
             4 |       2 |        2
             4 |       3 |        1
    (12 rows)

## Parameters

Parameter | Type | Description
--- | --- | ---
edges_sql | `TEXT` | Edges SQL query as described above.
start_vids | `ARRAY[ANY-INTEGER]` | Array of identifiers of the vertices.
directed | `BOOLEAN` | (optional). When `false` the graph is considered as Undirected. Default is `true` which considers the graph as Directed.

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

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

## Additional Examples

Example

  Use with tsp

    SELECT * FROM pgr_TSP(
        $$
        SELECT * FROM pgr_bdDijkstraCostMatrix(
            'SELECT id, source, target, cost, reverse_cost FROM edge_table',
            (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 5),
            false
        )
        $$,
        randomize := false
    );
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |    1 |    0 |        0
       2 |    2 |    1 |        1
       3 |    3 |    1 |        2
       4 |    4 |    1 |        3
       5 |    1 |    3 |        6
    (5 rows)

## See Also

- pgr_bdDijkstra

- Cost Matrix - Category

- pgr_TSP

- The queries use the Sample Data network.

Indices and tables

- Index

- Search Page