pgr_bdDijkstraCost
pgr_bdDijkstraCost
— Returns the shortest path(s)’s cost using Bidirectional Dijkstra algorithm.
Availability:
- Version 3.2.0
- New proposed function:
- pgr_bdDijkstraCost(Combinations)
- Version 3.0.0
- Version 2.5.0
Description
The main characteristics are:
- 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 agg_cost the non included values (v, v) is 0
- When the starting vertex and ending vertex are the different and there is no path:
- The agg_cost the non included values (u, v) is \(\infty\)
- 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_bdDijkstraCost(Edges SQL, from_vid, to_vid [, directed])
pgr_bdDijkstraCost(Edges SQL, from_vid, to_vids [, directed])
pgr_bdDijkstraCost(Edges SQL, from_vids, to_vid [, directed])
pgr_bdDijkstraCost(Edges SQL, from_vids, to_vids [, directed])
pgr_bdDijkstraCost(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Using default
pgr_bdDijkstraCost(Edges SQL, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(2\) to vertex \(3\) on a directed graph |
SELECT * FROM pgr_bdDijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 3
);
start_vid | end_vid | agg_cost
-----------+---------+----------
2 | 3 | 5
(1 row)
One to One
pgr_bdDijkstraCost(Edges SQL, from_vid, to_vid [, directed])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(2\) to vertex \(3\) on an undirected graph |
SELECT * FROM pgr_bdDijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 3,
false
);
start_vid | end_vid | agg_cost
-----------+---------+----------
2 | 3 | 1
(1 row)
One to Many
pgr_bdDijkstraCost(Edges SQL, from_vid, to_vids [, directed])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertex \(2\) to vertices \(\{3, 11\}\) on a directed graph |
SELECT * FROM pgr_bdDijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, ARRAY[3, 11]);
start_vid | end_vid | agg_cost
-----------+---------+----------
2 | 3 | 5
2 | 11 | 3
(2 rows)
Many to One
pgr_bdDijkstraCost(Edges SQL, from_vids, to_vids [, directed])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Example: | From vertices \(\{2, 7\}\) to vertex \(3\) on a directed graph |
SELECT * FROM pgr_bdDijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2, 7], 3);
start_vid | end_vid | agg_cost
-----------+---------+----------
2 | 3 | 5
7 | 3 | 6
(2 rows)
Many to Many
pgr_bdDijkstraCost(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 \(\{2, 7\}\) to vertices \(\{3, 11\}\) on a directed graph |
SELECT * FROM pgr_bdDijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[2, 7], ARRAY[3, 11]);
start_vid | end_vid | agg_cost
-----------+---------+----------
2 | 3 | 5
2 | 11 | 3
7 | 3 | 6
7 | 11 | 4
(4 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 a directed graph. |
SELECT * FROM pgr_bdDijkstraCost(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
'SELECT * FROM ( VALUES (2, 3), (7, 11) ) AS t(source, target)');
start_vid | end_vid | agg_cost
-----------+---------+----------
2 | 3 | 5
7 | 11 | 4
(2 rows)
Parameters
Parameter |
Type |
Default |
Description |
Edges SQL |
TEXT |
|
Edges query as described below |
Combinations SQL |
TEXT |
|
Combinations query 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. |
directed |
BOOLEAN |
true |
- When
true Graph is considered Directed
- When
false the graph is considered as Undirected.
|
Inner queries
Edges query
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)
- When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
|
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 query
Column |
Type |
Default |
Description |
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. |
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
Result Columns
Returns 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 . |
See Also
Indices and tables