pgr_bdDijkstra - Bi-directional Dijkstra Shortest Path

Name

pgr_bdDijkstra - Returns the shortest path using Bidirectional Dijkstra algorithm.

Synopsis

This is a bi-directional Dijkstra search algorithm. It searchs from the source toward the distination and at the same time from the destination to the source and terminates whe these to searchs meet in the middle. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.

pgr_costResult[] pgr_bdDijkstra(sql text, source integer, target integer,
                                directed boolean, 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 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

  • New in version 2.0.0

Examples

  • Without reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdDijkstra(
        'SELECT id, source, target, cost FROM edge_table',
        4, 10, false, false
    );

     seq | node | edge | cost
    -----+------+------+------
       0 |    4 |    3 |    0
       1 |    3 |    5 |    1
       2 |    6 |   11 |    1
       3 |   11 |   12 |    0
       4 |   10 |   -1 |    0
    (5 rows)
  • With reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdDijkstra(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        4, 10, true, true
    );

     seq | node | edge | cost
    -----+------+------+------
       0 |    4 |    3 |    1
       1 |    3 |    2 |    1
       2 |    2 |    4 |    1
       3 |    5 |   10 |    1
       4 |   10 |   -1 |    0
    (5 rows)

The queries use the Sample Data network.