pgr_dijkstraCost¶

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

Version 2.2.0
- New Official function

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

One to One¶

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

Example:	From vertex \(2\) to vertex \(3\) on an undirected graph

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)

One to Many¶

pgr_dijkstraCost(edges_sql, from_vid,  to_vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example:	From vertex \(2\) to vertices \(\{3, 11\}\) on a directed graph

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)

Many to One¶

 pgr_dijkstraCost(edges_sql, from_vids, to_vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example:	From vertices \(\{2, 7\}\) to vertex \(3\) on a directed graph

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)

Many to Many¶

pgr_dijkstraCost(edges_sql, from_vids, to_vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example:	From vertices \(\{2, 7\}\) to vertices \(\{3, 11\}\) on a directed graph

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)

Parameters¶

Parameter	Type	Default	Description
edges_sql	`TEXT`		Inner SQL query as described below.
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.

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

Return Columns¶

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)