# pgRouting Manual (2.1.0)

## pgr_ksp (V 2.0) - K-Shortest Path

## Name

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

## Synopsis

The K shortest path routing algorithm based on Yen’s algorithm. “K” is the number of shortest paths desired. Returns a set of pgr_costResult3 (seq, id1, id2, id3, cost) rows, that make up a path.

    pgr_costResult3[] pgr_ksp(sql text, source integer, target integer,
                             paths integer, has_rcost boolean);

Warning

This signature is being deprecated in version 2.1, Please use it without the `has_rcost` flag instead.

> - for undirected graph. `pgr_ksp(sql, source, target, distance, directed:=false)`
> - for directed graph. `pgr_ksp(sql, source, target, distance, directed:=true)`

See pgr_ksp - K-Shortest Path

## Description

sql:

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

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

id: | `int4` identifier of the edge
source: | `int4` identifier of the source vertex
target: | `int4` identifier of the target vertex
cost: | `float8` value, of the edge traversal cost. A negative cost will prevent the edge from being inserted in the graph.
reverse_cost: | (optional) the cost for the reverse traversal of the edge. This is only used when `has_rcost` the parameter is `true` (see the above remark about negative costs).

source: | `int4` id of the start point
target: | `int4` id of the end point
paths: | `int4` number of alternative routes
has_rcost: | if `true`, the `reverse_cost` column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

Returns set of pgr_costResult[]:

seq: | sequence for ording the results
id1: | route ID
id2: | node ID
id3: | edge ID (`0` for the last row)
cost: | cost to traverse from `id2` using `id3`

KSP code base taken from http://code.google.com/p/k-shortest-paths/source.

History

- New in version 2.0.0

## Examples

- Without `reverse_cost`

     SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
      FROM pgr_ksp(
        'SELECT id, source, target, cost FROM edge_table',
        7, 12, 2, false
      );
     seq | route | node | edge | cost
    -----+-------+------+------+------
       0 |     0 |    7 |    6 |    1
       1 |     0 |    8 |    7 |    1
       2 |     0 |    5 |    8 |    1
       3 |     0 |    6 |    9 |    1
       4 |     0 |    9 |   15 |    1
       5 |     0 |   12 |   -1 |    0
       6 |     1 |    7 |    6 |    1
       7 |     1 |    8 |    7 |    1
       8 |     1 |    5 |    8 |    1
       9 |     1 |    6 |   11 |    1
      10 |     1 |   11 |   13 |    1
      11 |     1 |   12 |   -1 |    0
    (12 rows)

- With `reverse_cost`

     SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
      FROM pgr_ksp(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        7, 12, 2, true
      );
     seq | route | node | edge | cost
    -----+-------+------+------+------
       0 |     0 |    7 |    6 |    1
       1 |     0 |    8 |    7 |    1
       2 |     0 |    5 |    8 |    1
       3 |     0 |    6 |    9 |    1
       4 |     0 |    9 |   15 |    1
       5 |     0 |   12 |   -1 |    0
       6 |     1 |    7 |    6 |    1
       7 |     1 |    8 |    7 |    1
       8 |     1 |    5 |    8 |    1
       9 |     1 |    6 |   11 |    1
      10 |     1 |   11 |   13 |    1
      11 |     1 |   12 |   -1 |    0
    (12 rows)

The queries use the Sample Data network.

## See Also

- pgr_costResult3[] - Multiple Path Results with Cost
- http://en.wikipedia.org/wiki/K_shortest_path_routing