pgr_ksp¶
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 |
|
|
| reverse_cost | ANY-NUMERICAL | -1 |
|
Where:
| ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
|---|---|
| ANY-NUMERICAL: | 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.
Additional Examples¶
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)
See Also¶
Indices and tables