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

``` 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.

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

### Return Columns

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 ``` .

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