pgr_dijkstraVia
- Proposed¶
pgr_dijkstraVia
— Route that goes through a list of vertices.
Warning
Proposed functions for next mayor release.
- They are not officially in the current release.
- They will likely officially be part of the next mayor release:
- The functions make use of ANY-INTEGER and ANY-NUMERICAL
- Name might not change. (But still can)
- Signature might not change. (But still can)
- Functionality might not change. (But still can)
- pgTap tests have being done. But might need more.
- Documentation might need refinement.
Availability
- Version 2.2.0
- New proposed function
Description¶
Given a list of vertices and a graph, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all \(i < size\_of(via\;vertices)\).
Route: | is a sequence of paths. |
---|---|
Path: | is a section of the route. |
Signatures¶
One Via¶
pgr_dijkstraVia(Edges SQL, via vertices [, directed] [, strict] [, U_turn_on_edge]) - Proposed on v2.2 RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid, node, edge, cost, agg_cost, route_agg_cost) OR EMPTY SET
Example: | Find the route that visits the vertices \(\{5, 1, 8\}\) in that order on an directed graph. |
---|
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 1, 8]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 5 | 1 | 5 | 1 | 1 | 0 | 0
2 | 1 | 2 | 5 | 1 | 6 | 4 | 1 | 1 | 1
3 | 1 | 3 | 5 | 1 | 7 | 7 | 1 | 2 | 2
4 | 1 | 4 | 5 | 1 | 3 | 6 | 1 | 3 | 3
5 | 1 | 5 | 5 | 1 | 1 | -1 | 0 | 4 | 4
6 | 2 | 1 | 1 | 8 | 1 | 6 | 1 | 0 | 4
7 | 2 | 2 | 1 | 8 | 3 | 7 | 1 | 1 | 5
8 | 2 | 3 | 1 | 8 | 7 | 10 | 1 | 2 | 6
9 | 2 | 4 | 1 | 8 | 8 | -2 | 0 | 3 | 7
(9 rows)
Parameters¶
Parameter | Type | Default | Description |
---|---|---|---|
Edges SQL | TEXT |
SQL query as described. | |
via vertices | ARRAY[ ANY-INTEGER ] |
Array of ordered vertices identifiers that are going to be visited. |
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
directed |
BOOLEAN |
true |
|
Via optional parameters¶
Parameter | Type | Default | Description |
---|---|---|---|
strict |
BOOLEAN |
false |
|
U_turn_on_edge |
BOOLEAN |
true |
|
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 (
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Result Columns¶
Column | Type | Description |
---|---|---|
seq |
INTEGER |
Sequential value starting from 1. |
path_id |
INTEGER |
Identifier of a path. Has value 1 for the first path. |
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 of the path. |
end_vid |
BIGINT |
Identifier of the ending vertex of the path. |
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
|
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 . |
route_agg_cost |
FLOAT |
Total cost from start_vid of seq = 1 to end_vid of the
current seq . |
Additional Examples¶
All this examples are about the route that visits the vertices \(\{5, 7, 1, 8, 15\}\) in that order on a directed graph.
The main query¶
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 7, 1, 8, 15]);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 | 1 | 1 | 5 | 7 | 5 | 1 | 1 | 0 | 0
2 | 1 | 2 | 5 | 7 | 6 | 4 | 1 | 1 | 1
3 | 1 | 3 | 5 | 7 | 7 | -1 | 0 | 2 | 2
4 | 2 | 1 | 7 | 1 | 7 | 7 | 1 | 0 | 2
5 | 2 | 2 | 7 | 1 | 3 | 6 | 1 | 1 | 3
6 | 2 | 3 | 7 | 1 | 1 | -1 | 0 | 2 | 4
7 | 3 | 1 | 1 | 8 | 1 | 6 | 1 | 0 | 4
8 | 3 | 2 | 1 | 8 | 3 | 7 | 1 | 1 | 5
9 | 3 | 3 | 1 | 8 | 7 | 10 | 1 | 2 | 6
10 | 3 | 4 | 1 | 8 | 8 | -1 | 0 | 3 | 7
11 | 4 | 1 | 8 | 15 | 8 | 12 | 1 | 0 | 7
12 | 4 | 2 | 8 | 15 | 12 | 13 | 1 | 1 | 8
13 | 4 | 3 | 8 | 15 | 17 | 15 | 1 | 2 | 9
14 | 4 | 4 | 8 | 15 | 16 | 16 | 1 | 3 | 10
15 | 4 | 5 | 8 | 15 | 15 | -2 | 0 | 4 | 11
(15 rows)
Aggregate cost of the third path.¶
SELECT agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge <0;
agg_cost
----------
3
(1 row)
Route’s aggregate cost of the route at the end of the third path.¶
SELECT route_agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
7
(1 row)
Nodes visited in the route.¶
SELECT row_number() over () as node_seq, node
FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 7, 1, 8, 15])
WHERE edge <> -1 ORDER BY seq;
node_seq | node
----------+------
1 | 5
2 | 6
3 | 7
4 | 3
5 | 1
6 | 3
7 | 7
8 | 8
9 | 12
10 | 17
11 | 16
12 | 15
(12 rows)
The aggregate costs of the route when the visited vertices are reached.¶
SELECT path_id, route_agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
path_id | route_agg_cost
---------+----------------
1 | 2
2 | 4
3 | 7
4 | 11
(4 rows)
Status of “passes in front” or “visits” of the nodes.¶
SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN 'visits'
ELSE 'passes in front'
END as status
FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edges order by id',
ARRAY[5, 7, 1, 8, 15])
WHERE agg_cost <> 0 or seq = 1;
seq | route_agg_cost | node | agg_cost | status
-----+----------------+------+----------+-----------------
1 | 0 | 5 | 0 | passes in front
2 | 1 | 6 | 1 | passes in front
3 | 2 | 7 | 2 | visits
5 | 3 | 3 | 1 | passes in front
6 | 4 | 1 | 2 | visits
8 | 5 | 3 | 1 | passes in front
9 | 6 | 7 | 2 | passes in front
10 | 7 | 8 | 3 | visits
12 | 8 | 12 | 1 | passes in front
13 | 9 | 17 | 2 | passes in front
14 | 10 | 16 | 3 | passes in front
15 | 11 | 15 | 4 | passes in front
(12 rows)
See Also¶
- Via - Category.
- Dijkstra - Family of functions.
- Sample Data network.
- https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Indices and tables