pgr_bdDijkstra¶
pgr_bdDijkstra — Returns the shortest path using Bidirectional Dijkstra
algorithm.
Boost Graph Inside¶
Availability:
Version 3.2.0
New proposed signature:
pgr_bdDijkstra(Combinations)
Version 3.0.0
Official function
Version 2.5.0
New Proposed functions:
pgr_bdDijkstra(One to Many)pgr_bdDijkstra(Many to One)pgr_bdDijkstra(Many to Many)
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
directed])directed])directed])directed])(seq, path_seq, [start_vid], [end_vid], node, edge, cost, agg_cost)One to One¶
directed])(seq, path_seq, node, edge, cost, agg_cost)- 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¶
directed])(seq, path_seq, end_vid, node, edge, cost, agg_cost)- 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¶
directed])(seq, path_seq, start_vid, node, edge, cost, agg_cost)- 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¶
directed])(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- 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¶
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- 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 |
|---|---|---|
|
Edges SQL as described below |
|
|
Combinations SQL 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. |
Optional parameters¶
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
|---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinations SQL¶
Parameter |
Type |
Description |
|---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
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 |
|---|---|---|
|
|
Sequential value starting from 1. |
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. |
|
|
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
|
|
Identifier of the node in the path from |
|
|
Identifier of the edge used to go from |
|
|
Cost to traverse from |
|
|
Aggregate cost from |
Additional Examples¶
- 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)
See Also¶
Indices and tables