pgr_KSP - pgRouting Manual (3.4)
pgr_KSP
pgr_KSP
- Yen’s algorithm for K shortest paths using Dijkstra.
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
[directed,
heap_paths]
(seq,
path_id,
path_seq,
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 node edge cost agg_cost
-----+---------+----------+------+------+------+----------
1 1 1 6 4 1 0
2 1 2 7 10 1 1
3 1 3 8 12 1 2
4 1 4 12 13 1 3
5 1 5 17 -1 0 4
6 2 1 6 4 1 0
7 2 2 7 8 1 1
8 2 3 11 9 1 2
9 2 4 16 15 1 3
10 2 5 17 -1 0 4
(10 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 departure 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
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 start vid to end vid |
|
|
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 node edge cost agg_cost
-----+---------+----------+------+------+------+----------
1 1 1 6 4 1 0
2 1 2 7 10 1 1
3 1 3 8 12 1 2
4 1 4 12 13 1 3
5 1 5 17 -1 0 4
6 2 1 6 4 1 0
7 2 2 7 8 1 1
8 2 3 11 11 1 2
9 2 4 12 13 1 3
10 2 5 17 -1 0 4
11 3 1 6 4 1 0
12 3 2 7 8 1 1
13 3 3 11 9 1 2
14 3 4 16 15 1 3
15 3 5 17 -1 0 4
16 4 1 6 2 1 0
17 4 2 10 5 1 1
18 4 3 11 9 1 2
19 4 4 16 15 1 3
20 4 5 17 -1 0 4
(20 rows)
See Also
Indices and tables