##  pgr_dijkstraCostMatrix 

 pgr_dijkstraCostMatrix  - Calculates a cost matrix using pgr_dijkstra .

Availability

• Version 3.0.0

• Official function

• Version 2.3.0

• New proposed function

### Description

Using Dijkstra algorithm, calculate and return a cost matrix.

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.

The main Characteristics are:

• Can be used as input to pgr_TSP .

• Use directly when the resulting matrix is symmetric and there is no $$\infty$$ value.

• It will be the users responsibility to make the matrix symmetric.

• By using geometric or harmonic average of the non symmetric values.

• By using max or min the non symmetric values.

• By setting the upper triangle to be the mirror image of the lower triangle.

• By setting the lower triangle to be the mirror image of the upper triangle.

• It is also the users responsibility to fix an $$\infty$$ value.

• Each function works as part of the family it belongs to.

• 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.

• When the starting vertex and ending vertex are the same, there is no path.

• The aggregate cost in 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 in the non included values (u, v) is $$\infty$$ .

• Let be the case the values returned are stored in a table:

• 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 vids are ignored.

• The returned values are ordered:

•  start_vid  ascending

•  end_vid  ascending

### Signatures

Summary

pgr_dijkstraCostMatrix( Edges SQL , start vids , [  directed  ])

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

Symmetric cost matrix for vertices $$\{5, 6, 10, 15\}$$ on an undirected graph

SELECT * FROM pgr_dijkstraCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edges',
(SELECT array_agg(id)
FROM vertices
WHERE id IN (5, 6, 10, 15)),
false);
start_vid  end_vid  agg_cost
-----------+---------+----------
5        6         1
5       10         2
5       15         3
6        5         1
6       10         1
6       15         2
10        5         2
10        6         1
10       15         1
15        5         3
15        6         2
15       10         1
(12 rows)



### Parameters

Column

Type

Description

 TEXT 

Edges SQL as described below

start vids

 ARRAY[BIGINT] 

Array of identifiers of starting 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 

### 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 :

Use with pgr_TSP .

SELECT * FROM pgr_TSP(
$$SELECT * FROM pgr_dijkstraCostMatrix( 'SELECT id, source, target, cost, reverse_cost FROM edges', (SELECT array_agg(id) FROM vertices WHERE id IN (5, 6, 10, 15)), false)$$);
NOTICE:  pgr_TSP no longer solving with simulated annaeling
HINT:  Ignoring annaeling parameters
seq  node  cost  agg_cost
-----+------+------+----------
1     5     0         0
2     6     1         1
3    10     1         2
4    15     1         3
5     5     3         6
(5 rows)