pgr_kDijkstra - Mutliple destination Shortest Path Dijkstra¶

Name¶

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

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_costResult3 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

New in version 2.0.0

Examples¶

Returning a cost result

SELECT seq, id1 AS source, id2 AS target, cost FROM pgr_kdijkstraCost(
    'SELECT id, source, target, cost FROM edge_table',
    10, array[4,12], false, false
);

 seq | source | target | cost
-----+--------+--------+------
   0 |     10 |      4 |    4
   1 |     10 |     12 |    2

SELECT seq, id1 AS path, id2 AS node, id3 AS edge, cost
  FROM pgr_kdijkstraPath(
      'SELECT id, source, target, cost FROM edge_table',
      10, array[4,12], false, false
);

 seq | path | node | edge | 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, source, target, 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;

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.0.0)