pgRouting Manual (2.2)

pgr_dijkstra (V 2.0)- Shortest Path Dijkstra

«  pgr_drivingDistance (V2.0)   ::   Contents   ::   pgr_ksp (V 2.0)  »

pgr_dijkstra (V 2.0)- Shortest Path Dijkstra

Name

pgr_dijkstra — Returns the shortest path using Dijkstra algorithm.

Synopsis

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.

pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target,
                           boolean directed, boolean has_rcost);

Warning

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

pgr_dijkstra(sql, source, target, directed)

See pgr_dijkstra

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:float8 (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

target:

int4 id of the end point

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.

Returns set of pgr_costResult[]:

seq:row sequence
id1:node ID
id2:edge ID (-1 for the last row)
cost:cost to traverse from id1 using id2

History

  • Renamed in version 2.0.0

Examples: Directed

  • Without reverse_cost
SELECT * FROM pgr_dijkstra(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table',
    2,3, true, false);
NOTICE:  Deprecated function
 seq | id1 | id2 | cost 
-----+-----+-----+------
(0 rows)
  • With reverse_cost
SELECT * FROM pgr_dijkstra(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table',
    2,3, true, true);
NOTICE:  Deprecated function
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |   8 |    1
   2 |   6 |   9 |    1
   3 |   9 |  16 |    1
   4 |   4 |   3 |    1
   5 |   3 |  -1 |    0
(6 rows)

Examples: Undirected

  • Without reverse_cost
SELECT * FROM pgr_dijkstra(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
     2, 3, false, false);
NOTICE:  Deprecated function
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |   8 |    1
   2 |   6 |   5 |    1
   3 |   3 |  -1 |    0
(4 rows)
  • With reverse_cost
SELECT * FROM pgr_dijkstra(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, reverse_cost FROM edge_table',
     2, 3, false, true);
NOTICE:  Deprecated function
 seq | id1 | id2 | cost 
-----+-----+-----+------
   0 |   2 |   2 |    1
   1 |   3 |  -1 |    0
(2 rows)

The queries use the Sample Data network.

«  pgr_drivingDistance (V2.0)   ::   Contents   ::   pgr_ksp (V 2.0)  »