# pgr_ksp¶

## Name¶

pgr_ksp — Returns the “K” shortest paths.

## Synopsis¶

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

## Signature Summary¶

pgr_ksp(edges_sql, start_vid, end_vid, K);
pgr_ksp(edges_sql, start_vid, end_vid, k, directed, heap_paths)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET


## Signatures¶

### Minimal Signature¶

pgr_ksp(edges_sql, start_vid, end_vid, K);
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET


### Complete Signature¶

pgr_ksp(edges_sql, start_vid, end_vid, k, directed, heap_paths)
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET


## Description of the Signatures¶

### Description of the edges_sql query¶

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
Column Type Description
edges_sql TEXT SQL query as described above.
start_vid BIGINT Identifier of the starting vertex.
end_vid BIGINT Identifier of the ending vertex.
k INTEGER The desiered number of paths.
directed BOOLEAN (optional). When false the graph is considered as Undirected. Default is true which considers the graph as Directed.
heap_paths BOOLEAN (optional). When true returns all the paths stored in the process heap. Default is false which only returns k pahts.

Roughly, if the shortest path has N edges, the heap will contain about than N * k paths for small value of k and k > 1.

### Description of the return values¶

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

Column Type Description
seq INTEGER Sequential value starting from 1.
path_seq INTEGER Relative position in the path of node and edge. Has value 1 for the beginning of a path.
path_id BIGINT Path identifier. The ordering of the paths For two paths i, j if i < j then agg_cost(i) <= agg_cost(j).
node BIGINT Identifier of the node in the path.
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 route.
cost FLOAT Cost to traverse from node using edge to the next node in the path sequence.
agg_cost FLOAT Aggregate cost from start_vid to node.

Warning

During the transition to 3.0, because pgr_ksp version 2.0 doesn’t have defined a directed flag nor a heap_path flag, when pgr_ksp is used with only one flag version 2.0 signature will be used.

### Examples to handle the one flag to choose signatures¶

The examples in this section use the following Graph 1: Directed, with cost and reverse cost

SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2,
true
);
NOTICE:  Deprecated function
seq | id1 | id2 | id3 | cost
-----+-----+-----+-----+------
0 |   0 |   2 |   4 |    1
1 |   0 |   5 |   8 |    1
2 |   0 |   6 |   9 |    1
3 |   0 |   9 |  15 |    1
4 |   0 |  12 |  -1 |    0
5 |   1 |   2 |   4 |    1
6 |   1 |   5 |   8 |    1
7 |   1 |   6 |  11 |    1
8 |   1 |  11 |  13 |    1
9 |   1 |  12 |  -1 |    0
(10 rows)

SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2,
directed:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
(10 rows)

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


### Examples for queries marked as directed with cost and reverse_cost columns¶

The examples in this section use the following Graph 1: Directed, with cost and reverse cost

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

SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, heap_paths:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
11 |       3 |        1 |    2 |    4 |    1 |        0
12 |       3 |        2 |    5 |   10 |    1 |        1
13 |       3 |        3 |   10 |   12 |    1 |        2
14 |       3 |        4 |   11 |   13 |    1 |        3
15 |       3 |        5 |   12 |   -1 |    0 |        4
(15 rows)

SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, true, true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
11 |       3 |        1 |    2 |    4 |    1 |        0
12 |       3 |        2 |    5 |   10 |    1 |        1
13 |       3 |        3 |   10 |   12 |    1 |        2
14 |       3 |        4 |   11 |   13 |    1 |        3
15 |       3 |        5 |   12 |   -1 |    0 |        4
(15 rows)


### Examples for queries marked as undirected with cost and reverse_cost columns¶

The examples in this section use the following Graph 2: Undirected, with cost and reverse cost

SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, directed:=false
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    2 |    1 |        0
2 |       1 |        2 |    3 |    3 |    1 |        1
3 |       1 |        3 |    4 |   16 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
(10 rows)

SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 12, 2, false, true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    2 |    1 |        0
2 |       1 |        2 |    3 |    3 |    1 |        1
3 |       1 |        3 |    4 |   16 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
11 |       3 |        1 |    2 |    4 |    1 |        0
12 |       3 |        2 |    5 |   10 |    1 |        1
13 |       3 |        3 |   10 |   12 |    1 |        2
14 |       3 |        4 |   11 |   13 |    1 |        3
15 |       3 |        5 |   12 |   -1 |    0 |        4
16 |       4 |        1 |    2 |    4 |    1 |        0
17 |       4 |        2 |    5 |   10 |    1 |        1
18 |       4 |        3 |   10 |   12 |    1 |        2
19 |       4 |        4 |   11 |   11 |    1 |        3
20 |       4 |        5 |    6 |    9 |    1 |        4
21 |       4 |        6 |    9 |   15 |    1 |        5
22 |       4 |        7 |   12 |   -1 |    0 |        6
(22 rows)


### Examples for queries marked as directed with cost column¶

The examples in this section use the following Graph 3: Directed, with cost

SELECT  * FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
2, 3, 2
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
(0 rows)

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

SELECT   * FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, heap_paths:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
11 |       3 |        1 |    2 |    4 |    1 |        0
12 |       3 |        2 |    5 |   10 |    1 |        1
13 |       3 |        3 |   10 |   12 |    1 |        2
14 |       3 |        4 |   11 |   13 |    1 |        3
15 |       3 |        5 |   12 |   -1 |    0 |        4
(15 rows)

SELECT  * FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, true, true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
11 |       3 |        1 |    2 |    4 |    1 |        0
12 |       3 |        2 |    5 |   10 |    1 |        1
13 |       3 |        3 |   10 |   12 |    1 |        2
14 |       3 |        4 |   11 |   13 |    1 |        3
15 |       3 |        5 |   12 |   -1 |    0 |        4
(15 rows)


### Examples for queries marked as undirected with cost column¶

The examples in this section use the following Graph 4: Undirected, with cost

SELECT  * FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, directed:=false
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
(10 rows)

SELECT  * FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, directed:=false, heap_paths:=true
);
seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
1 |       1 |        1 |    2 |    4 |    1 |        0
2 |       1 |        2 |    5 |    8 |    1 |        1
3 |       1 |        3 |    6 |    9 |    1 |        2
4 |       1 |        4 |    9 |   15 |    1 |        3
5 |       1 |        5 |   12 |   -1 |    0 |        4
6 |       2 |        1 |    2 |    4 |    1 |        0
7 |       2 |        2 |    5 |    8 |    1 |        1
8 |       2 |        3 |    6 |   11 |    1 |        2
9 |       2 |        4 |   11 |   13 |    1 |        3
10 |       2 |        5 |   12 |   -1 |    0 |        4
11 |       3 |        1 |    2 |    4 |    1 |        0
12 |       3 |        2 |    5 |   10 |    1 |        1
13 |       3 |        3 |   10 |   12 |    1 |        2
14 |       3 |        4 |   11 |   13 |    1 |        3
15 |       3 |        5 |   12 |   -1 |    0 |        4
(15 rows)