# pgr_dijkstraVia - Proposed¶

## Name¶

pgr_dijkstraVia — Using dijkstra algorithm, it finds the route that goes through a list of vertices.

Availability: 2.2.0

## Synopsis¶

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.

Note

This is a proposed function

## Signatrue Summary¶

pgr_dijkstraVia(edges_sql, via_vertices)
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


## Signatures¶

### Minimal Signature¶

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], 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 |    5 |    1 |        0 |              2
5 |       2 |        2 |         3 |       9 |    6 |    9 |    1 |        1 |              3
6 |       2 |        3 |         3 |       9 |    9 |   -2 |    0 |        2 |              4
(6 rows)



## Description of the Signature¶

### Description of the edges_sql query for dijkstra like functions¶

edges_sql: an SQL query, which should return a set of rows with the following columns:
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 SMALLINT, INTEGER, BIGINT, REAL, FLOAT

### Description of the parameters of the signatures¶

Parameter Type Default Description
edges_sql TEXT   SQL query as described above.
via_vertices ARRAY[ANY-INTEGER]   Array of ordered vertices identifiers that are going to be visited.
directed BOOLEAN true
• When true Graph is considered Directed
• When false the graph is considered as Undirected.
strict BOOLEAN false
• When false ignores missing paths returning all paths found
• When true if a path is missing stops and returns EMPTY SET
U_turn_on_edge BOOLEAN true
• When true departing from a visited vertex will not try to avoid using the edge used to reach it. In other words, U turn using the edge with same id is allowed.
• When false when a departing from a visited vertex tries to avoid using the edge used to reach it. In other words, U turn using the edge with same id is used when no other path is found.

### Description of the parameters of the signatures¶

Parameter Type Description
edges_sql TEXT SQL query as described above.
via_vertices ARRAY[ANY-INTEGER] Array of vertices identifiers
directed BOOLEAN (optional) Default is true (is directed). When set to false the graph is considered as Undirected
strict BOOLEAN (optional) ignores if a subsection of the route is missing and returns everything it found Default is true (is directed). When set to false the graph is considered as Undirected
U_turn_on_edge BOOLEAN (optional) Default is true (is directed). When set to false the graph is considered as Undirected

### Description of the return values¶

Returns set of (start_vid, end_vid, agg_cost)

Column Type Description
seq BIGINT Sequential value starting from 1.
path_pid BIGINT Identifier of the path.
path_seq BIGINT Sequential value starting from 1 for the 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 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 FLOAT Cost to traverse from node using edge to the next node in the route sequence.
agg_cost FLOAT Total cost from start_vid to end_vid of the path.
route_agg_cost FLOAT Total cost from start_vid of path_pid = 1 to end_vid of the current path_pid .

## 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