pgr_KSP¶
pgr_KSP — Yen’s algorithm for K shortest paths using Dijkstra.
Boost Graph Inside¶
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
pgr_KSP(Edges SQL, start vid, end vid, K, [options])
pgr_KSP(Edges SQL, start vid, end vids, K, [options])
pgr_KSP(Edges SQL, start vids, end vid, K, [options])
pgr_KSP(Edges SQL, start vids, end vids, K, [options])
pgr_KSP(Edges SQL, Combinations SQL, K, [options])
options:
[directed, heap_paths]Returns set of
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
One to One¶
pgr_KSP(Edges SQL, start vid, end vid, K, [options])
options:
[directed, heap_paths]Returns set of
(seq, path_id, path_seq, start_vid, end_vid, 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 | 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¶
pgr_KSP(Edges SQL, start vid, end vids, K, [options])
options:
[directed, heap_paths]Returns set of
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 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¶
pgr_KSP(Edges SQL, start vids, end vid, K, [options])
options:
[directed, heap_paths]Returns set of
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 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¶
pgr_KSP(Edges SQL, start vids, end vids, K, [options])
options:
[directed, heap_paths]Returns set of
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 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¶
pgr_KSP(Edges SQL, Combinations SQL, K, [options])
options:
[directed, heap_paths]Returns set of
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 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