pgr_ksp - K-Shortest Path¶
Synopsis¶
The K shortest path routing algorithm based on Yen’s algorithm. “K” is the number of shortest paths desired.
The minimal signature:
pgr_ksp(TEXT sql_q, BIGINT start_vid, BIGINT end_vid, INTEGER k);
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
The full signature:
pgr_ksp(TEXT edges_sql, BIGINT start_vid, BIGINT end_vid, INTEGER k,
BOOLEAN directed:=true, BOOLEAN heap_paths:=false);
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
Description of the SQL query¶
General description of the edges_sql
SELECT id, source, target, cost [,reverse_cost] FROM ...
| sql_q: | a SQL query, which returns a set of rows with the following columns:
|
|---|
Where:
| ANY-INTEGER: | smallint, int, bigint |
|---|---|
| ANY-NUMERICAL: | smallint, int, bigint, real, float |
Description of the parameters of the signatures¶
| sql_q: | TEXT SQL query as decribed above. |
|---|---|
| start_vid: | BIGINT id of the starting vertex. |
| end_vid: | BIGINT id 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)
| seq: | INT sequential number starting from 1. |
|---|---|
| path_seq: | INT relative position in the pathi of node and edge. Has value 1 for the begining 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 id of the node in the path. |
| edge: | BIGINT id 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 total 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 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 -- takes the (V2.0) signature (has_rcost = true and works on directed graph)
);
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 -- takes the new signature
);
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 | 0 | 1 | 2 | 4 | 1 | 0
2 | 0 | 2 | 5 | 8 | 1 | 1
3 | 0 | 3 | 6 | 9 | 1 | 2
4 | 0 | 4 | 9 | 15 | 1 | 3
5 | 0 | 5 | 12 | -1 | 0 | 4
6 | 1 | 1 | 2 | 4 | 1 | 0
7 | 1 | 2 | 5 | 8 | 1 | 1
8 | 1 | 3 | 6 | 11 | 1 | 2
9 | 1 | 4 | 11 | 13 | 1 | 3
10 | 1 | 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
);
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 | 9 | 1 | 2
9 | 2 | 4 | 9 | 15 | 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, directed:=false, heap_paths:=true
);
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 | 9 | 1 | 2
9 | 2 | 4 | 9 | 15 | 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
Empty path representation
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
);
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
);
SELECT * FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
2, 12, 2, false, 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)
The queries use the Sample Data network.
History
- New in version 2.0.0
- Added functionality version 2.1