pgr_KSP - pgRouting Manual (3.7)
pgr_KSP
pgr_KSP
- Yen’s algorithm for K shortest paths using Dijkstra.
Availability
Version 3.6.0
-
Result columns standarized to:
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) -
pgr_ksp(One to One)-
Added
start_vidandend_vidresult columns.
-
-
New overload functions:
-
pgr_ksp(One to Many) -
pgr_ksp(Many to One) -
pgr_ksp(Many to Many) -
pgr_ksp(Combinations)
-
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
[directed,
heap_paths]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
One to One
[directed,
heap_paths]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- 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 start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 6 17 6 4 1 0
2 1 2 6 17 7 10 1 1
3 1 3 6 17 8 12 1 2
4 1 4 6 17 12 13 1 3
5 1 5 6 17 17 -1 0 4
6 2 1 6 17 6 4 1 0
7 2 2 6 17 7 8 1 1
8 2 3 6 17 11 9 1 2
9 2 4 6 17 16 15 1 3
10 2 5 6 17 17 -1 0 4
(10 rows)
One to Many
[directed,
heap_paths]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Get 2 paths from vertex \(6\) to vertices \(\{10, 17\}\) on a directed graph.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
6, ARRAY[10, 17], 2);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 6 10 6 4 1 0
2 1 2 6 10 7 8 1 1
3 1 3 6 10 11 9 1 2
4 1 4 6 10 16 16 1 3
5 1 5 6 10 15 3 1 4
6 1 6 6 10 10 -1 0 5
7 2 1 6 10 6 4 1 0
8 2 2 6 10 7 10 1 1
9 2 3 6 10 8 12 1 2
10 2 4 6 10 12 13 1 3
11 2 5 6 10 17 15 1 4
12 2 6 6 10 16 16 1 5
13 2 7 6 10 15 3 1 6
14 2 8 6 10 10 -1 0 7
15 3 1 6 17 6 4 1 0
16 3 2 6 17 7 10 1 1
17 3 3 6 17 8 12 1 2
18 3 4 6 17 12 13 1 3
19 3 5 6 17 17 -1 0 4
20 4 1 6 17 6 4 1 0
21 4 2 6 17 7 8 1 1
22 4 3 6 17 11 9 1 2
23 4 4 6 17 16 15 1 3
24 4 5 6 17 17 -1 0 4
(24 rows)
Many to One
[directed,
heap_paths]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Get 2 paths from vertices \(\{6, 1\}\) to vertex \(17\) on a directed graph.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17, 2);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 1 17 1 6 1 0
2 1 2 1 17 3 7 1 1
3 1 3 1 17 7 10 1 2
4 1 4 1 17 8 12 1 3
5 1 5 1 17 12 13 1 4
6 1 6 1 17 17 -1 0 5
7 2 1 1 17 1 6 1 0
8 2 2 1 17 3 7 1 1
9 2 3 1 17 7 8 1 2
10 2 4 1 17 11 9 1 3
11 2 5 1 17 16 15 1 4
12 2 6 1 17 17 -1 0 5
13 3 1 6 17 6 4 1 0
14 3 2 6 17 7 10 1 1
15 3 3 6 17 8 12 1 2
16 3 4 6 17 12 13 1 3
17 3 5 6 17 17 -1 0 4
18 4 1 6 17 6 4 1 0
19 4 2 6 17 7 8 1 1
20 4 3 6 17 11 9 1 2
21 4 4 6 17 16 15 1 3
22 4 5 6 17 17 -1 0 4
(22 rows)
Many to Many
[directed,
heap_paths]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Get 2 paths vertices \(\{6, 1\}\) to vertices \(\{10, 17\}\) on a directed graph.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17], 2);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 1 10 1 6 1 0
2 1 2 1 10 3 7 1 1
3 1 3 1 10 7 8 1 2
4 1 4 1 10 11 9 1 3
5 1 5 1 10 16 16 1 4
6 1 6 1 10 15 3 1 5
7 1 7 1 10 10 -1 0 6
8 2 1 1 10 1 6 1 0
9 2 2 1 10 3 7 1 1
10 2 3 1 10 7 10 1 2
11 2 4 1 10 8 12 1 3
12 2 5 1 10 12 13 1 4
13 2 6 1 10 17 15 1 5
14 2 7 1 10 16 16 1 6
15 2 8 1 10 15 3 1 7
16 2 9 1 10 10 -1 0 8
17 3 1 1 17 1 6 1 0
18 3 2 1 17 3 7 1 1
19 3 3 1 17 7 10 1 2
20 3 4 1 17 8 12 1 3
21 3 5 1 17 12 13 1 4
22 3 6 1 17 17 -1 0 5
23 4 1 1 17 1 6 1 0
24 4 2 1 17 3 7 1 1
25 4 3 1 17 7 8 1 2
26 4 4 1 17 11 9 1 3
27 4 5 1 17 16 15 1 4
28 4 6 1 17 17 -1 0 5
29 5 1 6 10 6 4 1 0
30 5 2 6 10 7 8 1 1
31 5 3 6 10 11 9 1 2
32 5 4 6 10 16 16 1 3
33 5 5 6 10 15 3 1 4
34 5 6 6 10 10 -1 0 5
35 6 1 6 10 6 4 1 0
36 6 2 6 10 7 10 1 1
37 6 3 6 10 8 12 1 2
38 6 4 6 10 12 13 1 3
39 6 5 6 10 17 15 1 4
40 6 6 6 10 16 16 1 5
41 6 7 6 10 15 3 1 6
42 6 8 6 10 10 -1 0 7
43 7 1 6 17 6 4 1 0
44 7 2 6 17 7 10 1 1
45 7 3 6 17 8 12 1 2
46 7 4 6 17 12 13 1 3
47 7 5 6 17 17 -1 0 4
48 8 1 6 17 6 4 1 0
49 8 2 6 17 7 8 1 1
50 8 3 6 17 11 9 1 2
51 8 4 6 17 16 15 1 3
52 8 5 6 17 17 -1 0 4
(52 rows)
Combinations
[directed,
heap_paths]
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Using a combinations table on an directed graph
The combinations table:
SELECT source, target FROM combinations;
source target
--------+--------
5 6
5 10
6 5
6 15
6 14
(5 rows)
The query:
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations', 2);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 5 6 5 1 1 0
2 1 2 5 6 6 -1 0 1
3 2 1 5 10 5 1 1 0
4 2 2 5 10 6 4 1 1
5 2 3 5 10 7 8 1 2
6 2 4 5 10 11 9 1 3
7 2 5 5 10 16 16 1 4
8 2 6 5 10 15 3 1 5
9 2 7 5 10 10 -1 0 6
10 3 1 5 10 5 1 1 0
11 3 2 5 10 6 4 1 1
12 3 3 5 10 7 10 1 2
13 3 4 5 10 8 12 1 3
14 3 5 5 10 12 13 1 4
15 3 6 5 10 17 15 1 5
16 3 7 5 10 16 16 1 6
17 3 8 5 10 15 3 1 7
18 3 9 5 10 10 -1 0 8
19 4 1 6 5 6 1 1 0
20 4 2 6 5 5 -1 0 1
21 5 1 6 15 6 4 1 0
22 5 2 6 15 7 8 1 1
23 5 3 6 15 11 9 1 2
24 5 4 6 15 16 16 1 3
25 5 5 6 15 15 -1 0 4
26 6 1 6 15 6 4 1 0
27 6 2 6 15 7 10 1 1
28 6 3 6 15 8 12 1 2
29 6 4 6 15 12 13 1 3
30 6 5 6 15 17 15 1 4
31 6 6 6 15 16 16 1 5
32 6 7 6 15 15 -1 0 6
(32 rows)
Parameters
|
Column |
Type |
Description |
|---|---|---|
|
|
SQL query as described. |
|
|
start vid |
ANY-INTEGER |
Identifier of the departure vertex. |
|
end vid |
ANY-INTEGER |
Identifier of the destination vertex. |
|
K |
ANY-INTEGER |
Number of required paths. |
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT
Optional parameters
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
KSP Optional parameters
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
Inner Queries
Edges SQL
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinations SQL
|
Parameter |
Type |
Description |
|---|---|---|
|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT
Result columns
Returns set of
(seq,
path_id,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
|
Column |
Type |
Description |
|---|---|---|
|
|
|
Sequential value starting from 1 . |
|
|
|
Path identifier.
|
|
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
|
Identifier of the node in the path from
|
|
|
|
Identifier of the edge used to go from
|
|
|
|
Cost to traverse from
|
|
|
|
Aggregate cost from
start vid
to
|
Additional Examples
- 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 start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 6 17 6 4 1 0
2 1 2 6 17 7 10 1 1
3 1 3 6 17 8 12 1 2
4 1 4 6 17 12 13 1 3
5 1 5 6 17 17 -1 0 4
6 2 1 6 17 6 4 1 0
7 2 2 6 17 7 8 1 1
8 2 3 6 17 11 11 1 2
9 2 4 6 17 12 13 1 3
10 2 5 6 17 17 -1 0 4
11 3 1 6 17 6 4 1 0
12 3 2 6 17 7 8 1 1
13 3 3 6 17 11 9 1 2
14 3 4 6 17 16 15 1 3
15 3 5 6 17 17 -1 0 4
16 4 1 6 17 6 2 1 0
17 4 2 6 17 10 5 1 1
18 4 3 6 17 11 9 1 2
19 4 4 6 17 16 15 1 3
20 4 5 6 17 17 -1 0 4
(20 rows)
- Example :
-
Get 2 paths using combinations table on an undirected graph
Also get the paths in the heap.
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations', 2, directed => false, heap_paths => true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 5 6 5 1 1 0
2 1 2 5 6 6 -1 0 1
3 2 1 5 10 5 1 1 0
4 2 2 5 10 6 2 1 1
5 2 3 5 10 10 -1 0 2
6 3 1 5 10 5 1 1 0
7 3 2 5 10 6 4 1 1
8 3 3 5 10 7 8 1 2
9 3 4 5 10 11 5 1 3
10 3 5 5 10 10 -1 0 4
11 4 1 6 5 6 1 1 0
12 4 2 6 5 5 -1 0 1
13 5 1 6 15 6 2 1 0
14 5 2 6 15 10 3 1 1
15 5 3 6 15 15 -1 0 2
16 6 1 6 15 6 4 1 0
17 6 2 6 15 7 8 1 1
18 6 3 6 15 11 9 1 2
19 6 4 6 15 16 16 1 3
20 6 5 6 15 15 -1 0 4
21 7 1 6 15 6 2 1 0
22 7 2 6 15 10 5 1 1
23 7 3 6 15 11 9 1 2
24 7 4 6 15 16 16 1 3
25 7 5 6 15 15 -1 0 4
(25 rows)
- Example :
-
Get 2 paths from vertices \(\{6, 1\}\) to vertex \(17\) on a undirected graph.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17, 2, directed => false);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 1 17 1 6 1 0
2 1 2 1 17 3 7 1 1
3 1 3 1 17 7 10 1 2
4 1 4 1 17 8 12 1 3
5 1 5 1 17 12 13 1 4
6 1 6 1 17 17 -1 0 5
7 2 1 1 17 1 6 1 0
8 2 2 1 17 3 7 1 1
9 2 3 1 17 7 8 1 2
10 2 4 1 17 11 9 1 3
11 2 5 1 17 16 15 1 4
12 2 6 1 17 17 -1 0 5
13 3 1 6 17 6 4 1 0
14 3 2 6 17 7 10 1 1
15 3 3 6 17 8 12 1 2
16 3 4 6 17 12 13 1 3
17 3 5 6 17 17 -1 0 4
18 4 1 6 17 6 4 1 0
19 4 2 6 17 7 8 1 1
20 4 3 6 17 11 11 1 2
21 4 4 6 17 12 13 1 3
22 4 5 6 17 17 -1 0 4
(22 rows)
- Example :
-
Get 2 paths vertices \(\{6, 1\}\) to vertices \(\{10, 17\}\) on a directed graph.
Also get the paths in the heap.
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17], 2, heap_paths => true);
seq path_id path_seq start_vid end_vid node edge cost agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 1 1 1 10 1 6 1 0
2 1 2 1 10 3 7 1 1
3 1 3 1 10 7 8 1 2
4 1 4 1 10 11 9 1 3
5 1 5 1 10 16 16 1 4
6 1 6 1 10 15 3 1 5
7 1 7 1 10 10 -1 0 6
8 2 1 1 10 1 6 1 0
9 2 2 1 10 3 7 1 1
10 2 3 1 10 7 10 1 2
11 2 4 1 10 8 12 1 3
12 2 5 1 10 12 13 1 4
13 2 6 1 10 17 15 1 5
14 2 7 1 10 16 16 1 6
15 2 8 1 10 15 3 1 7
16 2 9 1 10 10 -1 0 8
17 3 1 1 10 1 6 1 0
18 3 2 1 10 3 7 1 1
19 3 3 1 10 7 8 1 2
20 3 4 1 10 11 11 1 3
21 3 5 1 10 12 13 1 4
22 3 6 1 10 17 15 1 5
23 3 7 1 10 16 16 1 6
24 3 8 1 10 15 3 1 7
25 3 9 1 10 10 -1 0 8
26 4 1 1 17 1 6 1 0
27 4 2 1 17 3 7 1 1
28 4 3 1 17 7 10 1 2
29 4 4 1 17 8 12 1 3
30 4 5 1 17 12 13 1 4
31 4 6 1 17 17 -1 0 5
32 5 1 1 17 1 6 1 0
33 5 2 1 17 3 7 1 1
34 5 3 1 17 7 8 1 2
35 5 4 1 17 11 11 1 3
36 5 5 1 17 12 13 1 4
37 5 6 1 17 17 -1 0 5
38 6 1 1 17 1 6 1 0
39 6 2 1 17 3 7 1 1
40 6 3 1 17 7 8 1 2
41 6 4 1 17 11 9 1 3
42 6 5 1 17 16 15 1 4
43 6 6 1 17 17 -1 0 5
44 7 1 6 10 6 4 1 0
45 7 2 6 10 7 8 1 1
46 7 3 6 10 11 9 1 2
47 7 4 6 10 16 16 1 3
48 7 5 6 10 15 3 1 4
49 7 6 6 10 10 -1 0 5
50 8 1 6 10 6 4 1 0
51 8 2 6 10 7 10 1 1
52 8 3 6 10 8 12 1 2
53 8 4 6 10 12 13 1 3
54 8 5 6 10 17 15 1 4
55 8 6 6 10 16 16 1 5
56 8 7 6 10 15 3 1 6
57 8 8 6 10 10 -1 0 7
58 9 1 6 10 6 4 1 0
59 9 2 6 10 7 8 1 1
60 9 3 6 10 11 11 1 2
61 9 4 6 10 12 13 1 3
62 9 5 6 10 17 15 1 4
63 9 6 6 10 16 16 1 5
64 9 7 6 10 15 3 1 6
65 9 8 6 10 10 -1 0 7
66 10 1 6 17 6 4 1 0
67 10 2 6 17 7 10 1 1
68 10 3 6 17 8 12 1 2
69 10 4 6 17 12 13 1 3
70 10 5 6 17 17 -1 0 4
71 11 1 6 17 6 4 1 0
72 11 2 6 17 7 8 1 1
73 11 3 6 17 11 11 1 2
74 11 4 6 17 12 13 1 3
75 11 5 6 17 17 -1 0 4
76 12 1 6 17 6 4 1 0
77 12 2 6 17 7 8 1 1
78 12 3 6 17 11 9 1 2
79 12 4 6 17 16 15 1 3
80 12 5 6 17 17 -1 0 4
(80 rows)
See Also
Indices and tables