# pgRouting Manual (2.1.0)

## pgr_ksp - K-Shortest Path

## Name

`pgr_ksp` — Returns the “K” shortest paths.

Boost Graph Inside

## Synopsis

The K shortest path routing algorithm based on Yen’s algorithm. “K” is the number of shortest paths desired.

The minimal signature:

    pgr_ksp(TEXT sql_q, BIGINT start_vid, BIGINT end_vid, INTEGER k);
      RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET

The full signature:

    pgr_ksp(TEXT edges_sql, BIGINT start_vid, BIGINT end_vid, INTEGER k,
          BOOLEAN directed:=true, BOOLEAN heap_paths:=false);
      RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost) or EMPTY SET

## Description of the SQL query

General description of the `edges_sql`

    SELECT id, source, target, cost [,reverse_cost] FROM ...

sql_q:

a SQL query, which returns a set of rows with the following columns:

id: | `ANY-INTEGER` identifier of the edge.
source: | `ANY-INTEGER` identifier of the source vertex of the edge.
target: | `ANY-INTEGER` identifier of the target vertex of the edge.
cost: | `ANY-NUMERICAL` value of the edge traversal cost. A negative cost will prevent the edge (`source`, `target`) from being inserted in the graph.
reverse_cost: | `ANY-NUMERICAL` (optional) the value for the reverse traversal of the edge. A negative cost will prevent the edge (`target`, `source`) from being inserted in the graph.

Where:

ANY-INTEGER: | smallint, int, bigint
ANY-NUMERICAL: | smallint, int, bigint, real, float

## Description of the parameters of the signatures

sql_q: | `TEXT` SQL query as decribed above.
start_vid: | `BIGINT` id of the starting vertex.
end_vid: | `BIGINT` id of the ending vertex.
k: | `INTEGER` The desiered number of paths.
directed: | `BOOLEAN` (optional). When `false` the graph is considered as Undirected. Default is `true` which considers the graph as Directed.
heap_paths: | `BOOLEAN` (optional). When `true` returns all the paths stored in the process heap. Default is `false` which only returns `k` pahts.

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`.

## Description of the return values

Returns set of `(seq, path_seq, path_id, node, edge, cost, agg_cost)`

seq: | `INT` sequential number starting from 1.
path_seq: | `INT` relative position in the pathi of `node` and `edge`. Has value 1 for the begining of a path.
path_id: | `BIGINT` path identifier. The ordering of the paths For two paths i, j if i < j then agg_cost(i) <= agg_cost(j).
node: | `BIGINT` id of the node in the path.
edge: | `BIGINT` id of the edge used to go from `node` to the next node in the path sequence. `-1` for the last node of the route.
cost: | `FLOAT` cost to traverse from `node` using `edge` to the next node in the path sequence.
agg_cost: | `FLOAT` total cost from `start_vid` to `node`.

Warning

During the transition to 3.0, because pgr_ksp version 2.0 doesn’t have defined a directed flag nor a heap_path flag, when pgr_ksp is used with only one flag version 2.0 will be used.

## Examples to handle the one flag to choose signatures

The examples in this section use the following Graph 1: Directed, with cost and reverse cost

     SELECT * FROM pgr_ksp(
       'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        2, 12, 2,
        true   -- takes the (V2.0) signature (has_rcost = true and works on directed graph)
     );
     seq | id1 | id2 | id3 | cost
    -----+-----+-----+-----+------
       0 |   0 |   2 |   4 |    1
       1 |   0 |   5 |   8 |    1
       2 |   0 |   6 |   9 |    1
       3 |   0 |   9 |  15 |    1
       4 |   0 |  12 |  -1 |    0
       5 |   1 |   2 |   4 |    1
       6 |   1 |   5 |   8 |    1
       7 |   1 |   6 |  11 |    1
       8 |   1 |  11 |  13 |    1
       9 |   1 |  12 |  -1 |    0
    (10 rows)

     SELECT * FROM pgr_ksp(
       'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        2, 12, 2,
        directed:=true   -- takes the new signature
     );

     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 |       0 |        1 |    2 |    4 |    1 |        0
         2 |       0 |        2 |    5 |    8 |    1 |        1
         3 |       0 |        3 |    6 |    9 |    1 |        2
         4 |       0 |        4 |    9 |   15 |    1 |        3
         5 |       0 |        5 |   12 |   -1 |    0 |        4
         6 |       1 |        1 |    2 |    4 |    1 |        0
         7 |       1 |        2 |    5 |    8 |    1 |        1
         8 |       1 |        3 |    6 |   11 |    1 |        2
         9 |       1 |        4 |   11 |   13 |    1 |        3
        10 |       1 |        5 |   12 |   -1 |    0 |        4
      (10 rows)

## Examples for queries marked as `directed` with `cost` and `reverse_cost` columns

The examples in this section use the following Graph 1: Directed, with cost and reverse cost

    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
    );

    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 `undirected` with `cost` and `reverse_cost` columns

The examples in this section use the following Graph 2: Undirected, with cost and reverse cost

    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 |    8 |    1 |        1
         8 |       2 |        3 |    6 |    9 |    1 |        2
         9 |       2 |        4 |    9 |   15 |    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, directed:=false, heap_paths:=true
     );

    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 |    9 |    1 |        2
         9 |       2 |        4 |    9 |   15 |    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)

## Examples for queries marked as `directed` with `cost` column

The examples in this section use the following Graph 3: Directed, with cost

Empty path representation

    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
     );

    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)

## Examples for queries marked as `undirected` with `cost` column

The examples in this section use the following Graph 4: Undirected, with cost

    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
     );

    SELECT * FROM pgr_ksp(
       'SELECT id, source, target, cost FROM edge_table',
        2, 12, 2, false, 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)

The queries use the Sample Data network.

History

- New in version 2.0.0
- Added functionality version 2.1

## See Also

- http://en.wikipedia.org/wiki/K_shortest_path_routing

Indices and tables

- Index
- Search Page