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
- Signature change
- 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
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 |
---|---|---|
Edges SQL | TEXT |
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 |
---|---|---|---|
directed |
BOOLEAN |
true |
|
KSP Optional parameters¶
Column | Type | Default | Description |
---|---|---|---|
heap_paths |
BOOLEAN |
false |
|
Inner Queries¶
Edges SQL¶
Column | Type | Default | Description |
---|---|---|---|
id |
ANY-INTEGER | Identifier of the edge. | |
source |
ANY-INTEGER | Identifier of the first end point vertex of the edge. | |
target |
ANY-INTEGER | Identifier of the second end point vertex of the edge. | |
cost |
ANY-NUMERICAL | Weight of the edge (source , target ) |
|
reverse_cost |
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 |
---|---|---|
seq |
INTEGER |
Sequential value starting from 1. |
path_id |
INTEGER |
Path identifier.
|
path_seq |
INTEGER |
Relative position in the path. Has value 1 for the beginning of a path. |
node |
BIGINT |
Identifier of the node in the path from start vid to end vid |
edge |
BIGINT |
Identifier of the edge used to go from node to the next node in the
path sequence. -1 for the last node of the path. |
cost |
FLOAT |
Cost to traverse from
|
agg_cost |
FLOAT |
Aggregate cost from start vid to node . |
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