pgr_dijkstraVia - Proposed - pgRouting Manual (3.3)
pgr_dijkstraVia - Proposed
pgr_dijkstraVia
- Using dijkstra algorithm, it finds the 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(vertex_via)\) .
The paths represents the sections of the route.
Signatures
Summary
pgr_dijkstraVia(edges_sql, via_vertices [, directed] [, strict] [, U_turn_on_edge])
RETURNS SET OF (seq, path_pid, path_seq, start_vid, end_vid,
node, edge, cost, agg_cost, route_agg_cost)
OR EMPTY SET
Using default
pgr_dijkstraVia(edges_sql, via_vertices)
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 \(\{ 1, 3, 9\}\) in that order
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 3, 9]
);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 1 3 1 1 1 0 0
2 1 2 1 3 2 4 1 1 1
3 1 3 1 3 5 8 1 2 2
4 1 4 1 3 6 9 1 3 3
5 1 5 1 3 9 16 1 4 4
6 1 6 1 3 4 3 1 5 5
7 1 7 1 3 3 -1 0 6 6
8 2 1 3 9 3 5 1 0 6
9 2 2 3 9 6 9 1 1 7
10 2 3 3 9 9 -2 0 2 8
(10 rows)
Complete Signature
pgr_dijkstraVia(edges_sql, via_vertices [, directed] [, strict] [, U_turn_on_edge])
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 \(\{ 1, 3, 9\}\) in that order on an undirected graph, avoiding U-turns when possible
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 3, 9]
);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 1 3 1 1 1 0 0
2 1 2 1 3 2 4 1 1 1
3 1 3 1 3 5 8 1 2 2
4 1 4 1 3 6 9 1 3 3
5 1 5 1 3 9 16 1 4 4
6 1 6 1 3 4 3 1 5 5
7 1 7 1 3 3 -1 0 6 6
8 2 1 3 9 3 5 1 0 6
9 2 2 3 9 6 9 1 1 7
10 2 3 3 9 9 -2 0 2 8
(10 rows)
/* -- q0 */
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 3, 9], false, strict:=true, U_turn_on_edge:=false
);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 1 3 1 1 1 0 0
2 1 2 1 3 2 2 1 1 1
3 1 3 1 3 3 -1 0 2 2
4 2 1 3 9 3 3 1 0 2
5 2 2 3 9 4 16 1 1 3
6 2 3 3 9 9 -2 0 2 4
(6 rows)
Parameters
|
Parameter |
Type |
Default |
Description |
|---|---|---|---|
|
edges_sql |
|
SQL query as described above. |
|
|
via_vertices |
|
Array of ordered vertices identifiers that are going to be visited. |
|
|
directed |
|
|
|
|
strict |
|
|
|
|
U_turn_on_edge |
|
|
|
Inner query
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
id |
|
Identifier of the edge. |
|
|
source |
|
Identifier of the first end point vertex of the edge. |
|
|
target |
|
Identifier of the second end point vertex of the edge. |
|
|
cost |
|
Weight of the edge (source, target)
|
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source) ,
|
Where:
- ANY-INTEGER :
-
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL :
-
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Return Columns
Returns set of
(start_vid,
end_vid,
agg_cost)
|
Column |
Type |
Description |
|---|---|---|
|
seq |
|
Sequential value starting from 1. |
|
path_pid |
|
Identifier of the path. |
|
path_seq |
|
Sequential value starting from 1 for the path. |
|
start_vid |
|
Identifier of the starting vertex of the path. |
|
end_vid |
|
Identifier of the ending vertex of the path. |
|
node |
|
Identifier of the node in the path from start_vid to end_vid. |
|
edge |
|
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. -2 for the last node of the route. |
|
cost |
|
Cost to traverse from
|
|
agg_cost |
|
Total cost from
|
|
route_agg_cost |
|
Total cost from
|
Additional Examples
- Example 1 :
-
Find the route that visits the vertices \(\{1, 5, 3, 9, 4\}\) in that order
SELECT * FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
);
seq path_id path_seq start_vid end_vid node edge cost agg_cost route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
1 1 1 1 5 1 1 1 0 0
2 1 2 1 5 2 4 1 1 1
3 1 3 1 5 5 -1 0 2 2
4 2 1 5 3 5 8 1 0 2
5 2 2 5 3 6 9 1 1 3
6 2 3 5 3 9 16 1 2 4
7 2 4 5 3 4 3 1 3 5
8 2 5 5 3 3 -1 0 4 6
9 3 1 3 9 3 5 1 0 6
10 3 2 3 9 6 9 1 1 7
11 3 3 3 9 9 -1 0 2 8
12 4 1 9 4 9 16 1 0 8
13 4 2 9 4 4 -2 0 1 9
(13 rows)
- Example 2 :
-
What’s the aggregate cost of the third path?
SELECT agg_cost FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE path_id = 3 AND edge <0;
agg_cost
----------
2
(1 row)
- Example 3 :
-
What’s the 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 edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE path_id = 3 AND edge < 0;
route_agg_cost
----------------
8
(1 row)
- Example 4 :
-
How are the nodes visited in the route?
SELECT row_number() over () as node_seq, node
FROM pgr_dijkstraVia(
'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE edge <> -1 ORDER BY seq;
node_seq node
----------+------
1 1
2 2
3 5
4 6
5 9
6 4
7 3
8 6
9 9
10 4
(10 rows)
- Example 5 :
-
What are 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 edge_table order by id',
ARRAY[1, 5, 3, 9, 4]
)
WHERE edge < 0;
path_id route_agg_cost
---------+----------------
1 2
2 6
3 8
4 9
(4 rows)
- Example 6 :
-
Show the route’s seq and aggregate cost and a status of "passes in front" or "visits" node \(9\)
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 edge_table order by id',
ARRAY[1, 5, 3, 9, 4])
WHERE node = 9 and (agg_cost <> 0 or seq = 1);
seq route_agg_cost node agg_cost status
-----+----------------+------+----------+-----------------
6 4 9 2 passes in front
11 8 9 2 visits
(2 rows)
ROLLBACK;
ROLLBACK
See Also
Indices and tables