pgr_ksp - Deprecated Signature¶

Warning

This function signature is deprecated!!!

That means it has been replaced by new signature(s)
This signature is no longer supported, and may be removed from future versions.
All code that use this function signature should be converted to use its replacement pgr_ksp.

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

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 * FROM pgr_ksp(
   'SELECT id, source, target, cost FROM edge_table order by id',
   7, 12, 2, false
 );
NOTICE:  Deprecated function
 seq | id1 | id2 | id3 | 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 * FROM pgr_ksp(
   'SELECT id, source, target, cost, reverse_cost FROM edge_table order by id',
   7, 12, 2, true
 );
NOTICE:  Deprecated function
 seq | id1 | id2 | id3 | 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.

pgRouting Manual (2.3)