pgr_kDijkstra - Mutliple destination Shortest Path Dijkstra¶

Name¶

pgr_kdijkstraCost - Returns the costs for K shortest paths using Dijkstra algorithm.

Warning

This functions is deprecated in 2.2. Use pgr_dijkstraCost instead.

pgr_kdijkstraPath - Returns the paths for K shortest paths using Dijkstra algorithm.

Warning

This function is deprecated in 2.2. Use pgr_dijkstra instead.

Synopsis¶

These functions allow you to have a single start node and multiple destination nodes and will compute the routes to all the destinations from the source node. Returns a set of pgr_costResult or pgr_costResult3. pgr_kdijkstraCost returns one record for each destination node and the cost is the total code of the route to that node. pgr_kdijkstraPath returns one record for every edge in that path from source to destination and the cost is to traverse that edge.

pgr_costResult[] pgr_kdijkstraCost(text sql, integer source,
                 integer[] targets, boolean directed, boolean has_rcost);

pgr_costResult3[] pgr_kdijkstraPath(text sql, integer source,
                  integer[] targets, boolean directed, boolean has_rcost);

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 the `directed` and `has_rcost` parameters are `true` (see the above remark about negative costs).

source:

int4 id of the start point

targets:

int4[] an array of ids of the end points

directed:

true if the graph is directed

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.

pgr_kdijkstraCost returns set of pgr_costResult[]:

seq:	row sequence
id1:	path vertex source id (this will always be source start point in the query).
id2:	path vertex target id
cost:	cost to traverse the path from `id1` to `id2`. Cost will be -1.0 if there is no path to that target vertex id.

pgr_kdijkstraPath returns set of pgr_costResult3[] - Multiple Path Results with Cost:

seq:	row sequence
id1:	path target id (identifies the target path).
id2:	path edge source node id
id3:	path edge id (`-1` for the last row)
cost:	cost to traverse this edge or -1.0 if there is no path to this target

History

Deprecated in version 2.0.0
New in version 2.0.0

Examples¶

Returning a cost result

SELECT * FROM pgr_kdijkstraCost(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
    10, array[4,12], false, false);
NOTICE:  Deprecated function. Use pgr_dijkstraCost instead.
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |  10 |   4 |    4
   1 |  10 |  12 |    2
(2 rows)

SELECT * FROM pgr_kdijkstraPath(
      'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
      10, array[4,12], false, false);
NOTICE:  Deprecated function: Use pgr_dijkstra instead.
 seq | id1 | id2 | id3 | cost 
-----+-----+-----+-----+------
   0 |   4 |  10 |  12 |    1
   1 |   4 |  11 |  13 |    1
   2 |   4 |  12 |  15 |    1
   3 |   4 |   9 |  16 |    1
   4 |   4 |   4 |  -1 |    0
   5 |  12 |  10 |  12 |    1
   6 |  12 |  11 |  13 |    1
   7 |  12 |  12 |  -1 |    0
(8 rows)

Returning a path result

SELECT id1 AS path, st_AStext(st_linemerge(st_union(b.the_geom))) AS the_geom
  FROM pgr_kdijkstraPath(
                  'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
                  10, array[4,12], false, false
            ) a,
            edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1;
NOTICE:  Deprecated function: Use pgr_dijkstra instead.
 path |            the_geom             
------+---------------------------------
    4 | LINESTRING(2 3,3 3,4 3,4 2,4 1)
   12 | LINESTRING(2 3,3 3,4 3)
(2 rows)

There is no assurance that the result above will be ordered in the direction of flow of the route, ie: it might be reversed. You will need to check if st_startPoint() of the route is the same as the start node location and if it is not then call st_reverse() to reverse the direction of the route. This behavior is a function of PostGIS functions st_linemerge() and st_union() and not pgRouting.

pgRouting Manual (2.2)