pgRouting Manual (2.2)

pgr_ksp (V 2.0)

«  pgr_dijkstra (V 2.0)- Shortest Path Dijkstra   ::   Contents   ::   Developers’s Functions  »

pgr_ksp (V 2.0)

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

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.

«  pgr_dijkstra (V 2.0)- Shortest Path Dijkstra   ::   Contents   ::   Developers’s Functions  »