pgr_dijkstraCost - pgRouting Manual (3.2)

Description

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.

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

Signatures

Summary

pgr_dijkstraCost(edges_sql, from_vid,  to_vid  [, directed])
pgr_dijkstraCost(edges_sql, from_vid,  to_vids [, directed])
pgr_dijkstraCost(edges_sql, from_vids, to_vid  [, directed])
pgr_dijkstraCost(edges_sql, from_vids, to_vids [, directed])
pgr_dijkstraCost(edges_sql, combinations_sql   [, directed]) -- Proposed on v3.1
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Using defaults

pgr_dijkstraCost(edges_sql, from_vid,  to_vid)
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example :

From vertex \(2\) to vertex \(3\) on a directed graph

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(edges_sql, from_vid,  to_vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

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(edges_sql, from_vid,  to_vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

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(edges_sql, from_vids, to_vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

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(edges_sql, from_vids, to_vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

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)

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

SELECT * FROM pgr_dijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    'SELECT source, target FROM combinations_table',
    FALSE
);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         1        2         1
         1        4         3
         2        1         1
         2        4         2
(4 rows)

Parameters

Inner query

Return Columns

Returns SET OF (start_vid, end_vid, agg_cost)

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)

Example 3 :

Four manually assigned (source, target) vertex combinations

SELECT * FROM pgr_dijkstraCost(
    'SELECT id, source, target, cost FROM edge_table',
    'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3), (11, 5)) AS combinations (source, target)',
    FALSE
);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         3
         2        5         1
        11        3         2
        11        5         2
(4 rows)

See Also

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

• Sample Data network.

Indices and tables

• Index

• Search Page