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.
Availability
 Version 3.1.0
 New Proposed functions:
 pgr_dijkstraCost(combinations)
 Version 2.2.0
 Supported versions:
current(3.1)
3.0
2.6
 Unsupported versions:
2.5
2.4
2.3
2.3
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)
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)
Combinations
pgr_dijkstraCost(TEXT edges_sql, TEXT combination_sql, BOOLEAN directed:=true);
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example:  Using a combinations table on an undirected graph 
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
Parameter 
Type 
Default 
Description 
Edges SQL 
TEXT 

Edges query as described below 
Combinations SQL 
TEXT 

Combinations 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
Edges query
Column 
Type 
Default 
Description 
id 
ANYINTEGER 

Identifier of the edge. 
source 
ANYINTEGER 

Identifier of the first end point vertex of the edge. 
target 
ANYINTEGER 

Identifier of the second end point vertex of the edge. 
cost 
ANYNUMERICAL 

Weight of the edge (source, target)
 When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost 
ANYNUMERICAL 
1 
Weight of the edge (target, source),
 When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 
ANYNUMERICAL:  SMALLINT, INTEGER, BIGINT, REAL, FLOAT 
Combinations query
Column 
Type 
Default 
Description 
source 
ANYINTEGER 

Identifier of the first end point vertex of the edge. 
target 
ANYINTEGER 

Identifier of the second end point vertex of the edge. 
Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 
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)
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
Indices and tables