## pgr_KSP

``` pgr_KSP ``` - Yen’s algorithm for K shortest paths using Dijkstra.

Availability

• Version 2.1.0

• Signature change

• Old signature no longer supported

• Version 2.0.0

• Official function

### Description

The K shortest path routing algorithm based on Yen’s algorithm. "K" is the number of shortest paths desired.

### Signatures

Summary

pgr_KSP( Edges SQL , start vid , end vid , K , [ options ])
options: ``` [directed, heap_paths] ```
RETURNS SET OF ``` (seq, path_id, path_seq, node, edge, cost, agg_cost) ```
OR EMPTY SET
Example :

Get 2 paths from \(6\) to \(17\) on a directed graph.

```SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 17, 2);
seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
1        1         1     6     4     1         0
2        1         2     7    10     1         1
3        1         3     8    12     1         2
4        1         4    12    13     1         3
5        1         5    17    -1     0         4
6        2         1     6     4     1         0
7        2         2     7     8     1         1
8        2         3    11     9     1         2
9        2         4    16    15     1         3
10        2         5    17    -1     0         4
(10 rows)

```

### Parameters

Column

Type

Description

``` TEXT ```

SQL query as described.

start vid

ANY-INTEGER

Identifier of the departure vertex.

end vid

ANY-INTEGER

Identifier of the departure vertex.

K

ANY-INTEGER

Number of required paths

Where:

ANY-INTEGER :

``` SMALLINT ``` , ``` INTEGER ``` , ``` BIGINT ```

#### Optional parameters

Column

Type

Default

Description

``` directed ```

``` BOOLEAN ```

``` true ```

• When ``` true ``` the graph is considered Directed

• When ``` false ``` the graph is considered as Undirected .

### KSP Optional parameters

Column

Type

Default

Description

``` heap_paths ```

``` BOOLEAN ```

``` false ```

• When ``` false ``` Returns at most K paths

• When ``` true ``` all the calculated paths while processing are returned.

• Roughly, when the shortest path has ``` N ``` edges, the heap will contain about than ``` N * K ``` paths for small value of ``` K ``` and ``` K > 5 ``` .

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

### Result Columns

Returns set of ``` (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) ```

Column

Type

Description

``` seq ```

``` INTEGER ```

Sequential value starting from 1 .

``` path_id ```

``` INTEGER ```

Path identifier.

• Has value 1 for the first of a path from start vid to end_vid

``` path_seq ```

``` INTEGER ```

Relative position in the path. Has value 1 for the beginning of a 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.

``` cost ```

``` FLOAT ```

Cost to traverse from ``` node ``` using ``` edge ``` to the next node in the path sequence.

• \(0\) for the last ``` node ``` of the path.

``` agg_cost ```

``` FLOAT ```

Aggregate cost from start vid to ``` node ``` .

Example :

Get 2 paths from \(6\) to \(17\) on an undirected graph

Also get the paths in the heap.

```SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 17, 2,
directed => false, heap_paths => true
);
seq  path_id  path_seq  node  edge  cost  agg_cost
-----+---------+----------+------+------+------+----------
1        1         1     6     4     1         0
2        1         2     7    10     1         1
3        1         3     8    12     1         2
4        1         4    12    13     1         3
5        1         5    17    -1     0         4
6        2         1     6     4     1         0
7        2         2     7     8     1         1
8        2         3    11    11     1         2
9        2         4    12    13     1         3
10        2         5    17    -1     0         4
11        3         1     6     4     1         0
12        3         2     7     8     1         1
13        3         3    11     9     1         2
14        3         4    16    15     1         3
15        3         5    17    -1     0         4
16        4         1     6     2     1         0
17        4         2    10     5     1         1
18        4         3    11     9     1         2
19        4         4    16    15     1         3
20        4         5    17    -1     0         4
(20 rows)

```