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
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 bellow. 
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 SQL:  an SQL query, which should return a set of rows with the following columns: 
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 
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)
See Also
Indices and tables