pgr_KSP - pgRouting Manual (3.2)
pgr_KSP
pgr_KSP
- Returns the "K" shortest paths.
Availability
-
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 [, directed] [, heap_paths])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET
Using defaults
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
- Example :
-
TBD
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
- Example :
-
TBD
Parameters
|
Column |
Type |
Description |
|---|---|---|
|
edges_sql |
|
SQL query as described above. |
|
start_vid |
|
Identifier of the starting vertex. |
|
end_vid |
|
Identifier of the ending vertex. |
|
k |
|
The desiered number of paths. |
|
directed |
|
(optional). When
|
|
heap_paths |
|
(optional). When
|
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
.
Inner query
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
id |
|
Identifier of the edge. |
|
|
source |
|
Identifier of the first end point vertex of the edge. |
|
|
target |
|
Identifier of the second end point vertex of the edge. |
|
|
cost |
|
Weight of the edge (source, target)
|
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source) ,
|
Where:
- ANY-INTEGER :
-
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL :
-
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Result Columns
Returns set of
(seq,
path_seq,
path_id,
node,
edge,
cost,
agg_cost)
|
Column |
Type |
Description |
|---|---|---|
|
seq |
|
Sequential value starting from 1 . |
|
path_seq |
|
Relative position in the path of
|
|
path_id |
|
Path identifier. The ordering of the paths For two paths i, j if i < j then agg_cost(i) <= agg_cost(j). |
|
node |
|
Identifier of the node in the path. |
|
edge |
|
Identifier of the edge used to go from
|
|
cost |
|
Cost to traverse from
|
|
agg_cost |
|
Aggregate cost from
|
Additional Examples
- Example :
-
To handle the one flag to choose signatures
The examples in this section use the following Network for queries marked as directed and cost and reverse_cost columns are used
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)
- Example :
-
For queries marked as
directedwithcostandreverse_costcolumns
The examples in this section use the following Network for queries marked as directed and cost and reverse_cost columns are used
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
undirectedwithcostandreverse_costcolumns
The examples in this section use the following Network for queries marked as undirected and cost and reverse_cost columns are used
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 10 1 1
8 2 3 10 12 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)
- Example :
-
For queries marked as
directedwithcostcolumn
The examples in this section use the following Network for queries marked as directed and only cost column is used
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)
- Example :
-
For queries marked as
undirectedwithcostcolumn
The examples in this section use the following Network for queries marked as undirected and only cost column is used
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