##  pgr_bdDijkstra 

 pgr_bdDijkstra  - Returns the shortest path(s) using Bidirectional Dijkstra algorithm.

Availability:

• Version 3.2.0

• Version 3.0.0

• Official function

• Version 2.5.0

• Version 2.4.0

• Signature change on  pgr_bdDijsktra  ( One to One )

• Old signature no longer supported

• Version 2.0.0

• Official  pgr_bdDijkstra  ( One to One )

### Description

The main characteristics are:

• 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 (worse case scenario): $$O((V \log V + E))$$

• For large graphs where there is a path bewtween the starting vertex and ending vertex:

• It is expected to terminate faster than pgr_dijkstra

### Signatures

Summary

pgr_bdDijkstra( Edges SQL , start vid , end vid , [  directed  ])
pgr_bdDijkstra( Edges SQL , start vid , end vids , [  directed  ])
pgr_bdDijkstra( Edges SQL , start vids , end vid , [  directed  ])
pgr_bdDijkstra( Edges SQL , start vids , end vids , [  directed  ])
pgr_bdDijkstra( Edges SQL , Combinations SQL , [  directed  ])
RETURNS SET OF  (seq, path_seq, [start_vid], [end_vid], node, edge, cost, agg_cost) 
OR EMPTY SET

#### One to One

pgr_bdDijkstra( Edges SQL , start vid , end vid , [  directed  ])
RETURNS SET OF  (seq, path_seq, node, edge, cost, agg_cost) 
OR EMPTY SET
Example :

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

SELECT * FROM pgr_bdDijkstra(
'select id, source, target, cost, reverse_cost from edges',
6, 10, true);
seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
1         1     6     4     1         0
2         2     7     8     1         1
3         3    11     9     1         2
4         4    16    16     1         3
5         5    15     3     1         4
6         6    10    -1     0         5
(6 rows)



#### One to Many

pgr_bdDijkstra( Edges SQL , start vid , end vids , [  directed  ])
RETURNS SET OF  (seq, path_seq, end_vid, node, edge, cost, agg_cost) 
OR EMPTY SET
Example :

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

SELECT * FROM pgr_bdDijkstra(
'select id, source, target, cost, reverse_cost from edges',
6, ARRAY[10, 17]);
seq  path_seq  end_vid  node  edge  cost  agg_cost
-----+----------+---------+------+------+------+----------
1         1       10     6     4     1         0
2         2       10     7     8     1         1
3         3       10    11     9     1         2
4         4       10    16    16     1         3
5         5       10    15     3     1         4
6         6       10    10    -1     0         5
7         1       17     6     4     1         0
8         2       17     7     8     1         1
9         3       17    11    11     1         2
10         4       17    12    13     1         3
11         5       17    17    -1     0         4
(11 rows)



#### Many to One

pgr_bdDijkstra( Edges SQL , start vids , end vid , [  directed  ])
RETURNS SET OF  (seq, path_seq, start_vid, node, edge, cost, agg_cost) 
OR EMPTY SET
Example :

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

SELECT * FROM pgr_bdDijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17);
seq  path_seq  start_vid  node  edge  cost  agg_cost
-----+----------+-----------+------+------+------+----------
1         1          1     1     6     1         0
2         2          1     3     7     1         1
3         3          1     7     8     1         2
4         4          1    11    11     1         3
5         5          1    12    13     1         4
6         6          1    17    -1     0         5
7         1          6     6     4     1         0
8         2          6     7     8     1         1
9         3          6    11    11     1         2
10         4          6    12    13     1         3
11         5          6    17    -1     0         4
(11 rows)



#### Many to Many

pgr_bdDijkstra( Edges SQL , start vids , end vids , [  directed  ])
RETURNS SET OF  (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) 
OR EMPTY SET
Example :

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

SELECT * FROM pgr_bdDijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17],
directed => false);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
1         1          1       10     1     6     1         0
2         2          1       10     3     7     1         1
3         3          1       10     7     4     1         2
4         4          1       10     6     2     1         3
5         5          1       10    10    -1     0         4
6         1          1       17     1     6     1         0
7         2          1       17     3     7     1         1
8         3          1       17     7     8     1         2
9         4          1       17    11    11     1         3
10         5          1       17    12    13     1         4
11         6          1       17    17    -1     0         5
12         1          6       10     6     2     1         0
13         2          6       10    10    -1     0         1
14         1          6       17     6     2     1         0
15         2          6       17    10     5     1         1
16         3          6       17    11    11     1         2
17         4          6       17    12    13     1         3
18         5          6       17    17    -1     0         4
(18 rows)



#### Combinations

pgr_bdDijkstra( Edges SQL , Combinations SQL , [  directed  ])
RETURNS SET OF  (seq, path_seq, start_vid, end_vid, node, edge, cost, 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_bdDijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations',
false);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
1         1          5        6     5     1     1         0
2         2          5        6     6    -1     0         1
3         1          5       10     5     1     1         0
4         2          5       10     6     2     1         1
5         3          5       10    10    -1     0         2
6         1          6        5     6     1     1         0
7         2          6        5     5    -1     0         1
8         1          6       15     6     2     1         0
9         2          6       15    10     3     1         1
10         3          6       15    15    -1     0         2
(10 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

Returns set of  (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) 

Column

Type

Description

 seq 

 INTEGER 

Sequential value starting from 1 .

 path_seq 

 INTEGER 

Relative position in the path. Has value 1 for the beginning of a path.

 start_vid 

 BIGINT 

Identifier of the starting vertex. Returned when multiple starting vetrices are in the query.

 end_vid 

 BIGINT 

Identifier of the ending vertex. Returned when multiple ending vertices are in the query.

 node 

 BIGINT 

Identifier of the node in the path from  start_vid  to  end_vid  .

 edge 

 BIGINT 

Identifier of the edge used to go from  node  to the next node in the path sequence. -1 for the last node of the path.

 cost 

 FLOAT 

Cost to traverse from  node  using  edge  to the next node in the path sequence.

 agg_cost 

 FLOAT 

Aggregate cost from  start_vid  to  node  .

Example 1 :

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

SELECT * FROM pgr_bdDijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
1         1          7       10     7     8     1         0
2         2          7       10    11     9     1         1
3         3          7       10    16    16     1         2
4         4          7       10    15     3     1         3
5         5          7       10    10    -1     0         4
6         1          7       15     7     8     1         0
7         2          7       15    11     9     1         1
8         3          7       15    16    16     1         2
9         4          7       15    15    -1     0         3
10         1         10        7    10     2     1         0
11         2         10        7     6     4     1         1
12         3         10        7     7    -1     0         2
13         1         10       15    10     5     1         0
14         2         10       15    11     9     1         1
15         3         10       15    16    16     1         2
16         4         10       15    15    -1     0         3
17         1         15        7    15     3     1         0
18         2         15        7    10     2     1         1
19         3         15        7     6     4     1         2
20         4         15        7     7    -1     0         3
21         1         15       10    15     3     1         0
22         2         15       10    10    -1     0         1
(22 rows)


Example 2 :

Making start vids the same as end vids .

SELECT * FROM pgr_bdDijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
1         1          7       10     7     8     1         0
2         2          7       10    11     9     1         1
3         3          7       10    16    16     1         2
4         4          7       10    15     3     1         3
5         5          7       10    10    -1     0         4
6         1          7       15     7     8     1         0
7         2          7       15    11     9     1         1
8         3          7       15    16    16     1         2
9         4          7       15    15    -1     0         3
10         1         10        7    10     2     1         0
11         2         10        7     6     4     1         1
12         3         10        7     7    -1     0         2
13         1         10       15    10     5     1         0
14         2         10       15    11     9     1         1
15         3         10       15    16    16     1         2
16         4         10       15    15    -1     0         3
17         1         15        7    15     3     1         0
18         2         15        7    10     2     1         1
19         3         15        7     6     4     1         2
20         4         15        7     7    -1     0         3
21         1         15       10    15     3     1         0
22         2         15       10    10    -1     0         1
(22 rows)


Example 3 :

Manually assigned vertex combinations.

SELECT * FROM pgr_bdDijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
seq  path_seq  start_vid  end_vid  node  edge  cost  agg_cost
-----+----------+-----------+---------+------+------+------+----------
1         1          6        7     6     4     1         0
2         2          6        7     7    -1     0         1
3         1          6       10     6     4     1         0
4         2          6       10     7     8     1         1
5         3          6       10    11     9     1         2
6         4          6       10    16    16     1         3
7         5          6       10    15     3     1         4
8         6          6       10    10    -1     0         5
9         1         12       10    12    13     1         0
10         2         12       10    17    15     1         1
11         3         12       10    16    16     1         2
12         4         12       10    15     3     1         3
13         5         12       10    10    -1     0         4
(13 rows)