pgr_bdDijkstraCostMatrix - pgRouting Manual (3.2)

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)

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

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

Inner query

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Returns SET OF (start_vid, end_vid, agg_cost)

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