pgr_bdDijkstra - pgRouting Manual (3.4)
pgr_bdDijkstra
pgr_bdDijkstra
- Returns the shortest path(s) using Bidirectional Dijkstra
algorithm.
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