## pgr_dijkstraCost

pgr_dijkstraCost - Total cost of the shortest path(s) using Dijkstra algorithm.

Availability

• Version 3.1.0

• Version 2.2.0

• New Official function

### Description

The pgr_dijkstraCost function sumarizes of the cost of the shortest path(s) using Dijkstra Algorithm.

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.

• Process is done only on edges with positive costs.

• A negative value on a cost column is interpreted as the edge does not exist.

• Values are returned when there is a path.

• When there is no path:

• When the starting vertex and ending vertex are the same.

• The aggregate cost of the non included values $$(v, v)$$ is $$0$$

• When the starting vertex and ending vertex are the different and there is no path:

• The aggregate cost the non included values $$(u, v)$$ is $$\infty$$

• For optimization purposes, any duplicated value in the starting vertices or on the ending vertices are ignored.

• Running time: $$O( start\ vids * (V \log V + E))$$

• It does not return a path.

• Returns the sum of the costs of the shortest path of each pair combination of nodes requested.

• Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid) .

• Depending on the function and its parameters, the results can be symmetric.

• The aggregate cost of $$(u, v)$$ is the same as for $$(v, u)$$ .

• Any duplicated value in the start or end vertex identifiers are ignored.

• The returned values are ordered:

• start_vid ascending

• end_vid ascending

### Signatures

Summary

pgr_dijkstraCost( Edges SQL , start vid , end vid , [ directed ])
pgr_dijkstraCost( Edges SQL , start vid , end vids , [ directed ])
pgr_dijkstraCost( Edges SQL , start vids , end vid , [ directed ])
pgr_dijkstraCost( Edges SQL , start vids , end vids , [ directed ])
pgr_dijkstraCost( Edges SQL , Combinations SQL , [ directed ])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

#### One to One

pgr_dijkstraCost( Edges SQL , start vid , end vid , [ directed ])

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example :

From vertex $$6$$ to vertex $$10$$ on a directed graph

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 10, true);
start_vid  end_vid  agg_cost
-----------+---------+----------
6       10         5
(1 row)

#### One to Many

pgr_dijkstraCost( Edges SQL , start vid , end vids , [ directed ])

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example :

From vertex $$6$$ to vertices $$\{10, 17\}$$ on a directed graph

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, ARRAY[10, 17]);
start_vid  end_vid  agg_cost
-----------+---------+----------
6       10         5
6       17         4
(2 rows)

#### Many to One

pgr_dijkstraCost( Edges SQL , start vids , end vid , [ directed ])

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example :

From vertices $$\{6, 1\}$$ to vertex $$17$$ on a directed graph

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 1], 17);
start_vid  end_vid  agg_cost
-----------+---------+----------
1       17         5
6       17         4
(2 rows)

#### Many to Many

pgr_dijkstraCost( Edges SQL , start vids , end vids , [ directed ])

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example :

From vertices $$\{6, 1\}$$ to vertices $$\{10, 17\}$$ on an undirected graph

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 1], ARRAY[10, 17],
directed => false);
start_vid  end_vid  agg_cost
-----------+---------+----------
1       10         4
1       17         5
6       10         1
6       17         4
(4 rows)

#### Combinations

pgr_dijkstraCost( Edges SQL , Combinations SQL , [ directed ])

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example :

Using a combinations table on an undirected graph

The combinations table:

SELECT source, target FROM combinations;
source  target
--------+--------
5       6
5      10
6       5
6      15
6      14
(5 rows)

The query:

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations',
false);
start_vid  end_vid  agg_cost
-----------+---------+----------
5        6         1
5       10         2
6        5         1
6       15         2
(4 rows)

### Parameters

Column

Type

Description

TEXT

Edges SQL as described below

TEXT

Combinations SQL 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.

#### Optional parameters

Column

Type

Default

Description

directed

BOOLEAN

true

• When true the graph is considered Directed

• When false the graph is considered as Undirected .

### Inner Queries

#### Edges SQL

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 )

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

#### Combinations SQL

Parameter

Type

Description

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

### Result Columns

Set of (start_vid, end_vid, agg_cost)

Column

Type

Description

start_vid

BIGINT

Identifier of the starting vertex.

end_vid

BIGINT

Identifier of the ending vertex.

agg_cost

FLOAT

Aggregate cost from start_vid to end_vid .

Example 1 :

Demonstration of repeated values are ignored, and result is sorted.

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
start_vid  end_vid  agg_cost
-----------+---------+----------
7       10         4
7       15         3
10        7         2
10       15         3
15        7         3
15       10         1
(6 rows)

Example 2 :

Making start_vids the same as end_vids

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
start_vid  end_vid  agg_cost
-----------+---------+----------
7       10         4
7       15         3
10        7         2
10       15         3
15        7         3
15       10         1
(6 rows)

Example 3 :

Manually assigned vertex combinations.

SELECT * FROM pgr_dijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
start_vid  end_vid  agg_cost
-----------+---------+----------
6        7         1
6       10         5
12       10         4
(3 rows)