pgr_dijkstraCost  pgRouting Manual (3.3)
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

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])
pgr_dijkstraCost(edges_sql, combinations_sql [, 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)
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 

Edges query as described below 

Combinations SQL 

Combinations query as described below 

start_vid 

Identifier of the starting vertex of the path. 

start_vids 

Array of identifiers of starting vertices. 

end_vid 

Identifier of the ending vertex of the path. 

end_vids 

Array of identifiers of ending vertices. 

directed 



Inner query
Edges query
Column 
Type 
Default 
Description 

id 

Identifier of the edge. 

source 

Identifier of the first end point vertex of the edge. 

target 

Identifier of the second end point vertex of the edge. 

cost 

Weight of the edge (source, target)


reverse_cost 

1 
Weight of the edge (target, source) ,

Where:
 ANYINTEGER :

SMALLINT, INTEGER, BIGINT
 ANYNUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Combinations query
Column 
Type 
Default 
Description 

source 

Identifier of the first end point vertex of the edge. 

target 

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 

Identifier of the starting vertex. 
end_vid 

Identifier of the ending vertex. 
agg_cost 

Aggregate cost from

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