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 ANYINTEGER and ANYNUMERICAL
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 Uturns when possible
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:
 ANYINTEGER
SMALLINT, INTEGER, BIGINT
 ANYNUMERICAL
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