pgr_bdDijkstraCost - pgRouting Manual (3.2)

Description

The main characteristics are:

• Process is done only on edges with positive costs.

• Values are returned when there is a path.

• When the starting vertex and ending vertex are the same, there is no path.

  • The agg_cost the non included values (v, v) is 0

• When the starting vertex and ending vertex are the different and there is no path:

  • The agg_cost the non included values (u, v) is \(\infty\)

• Running time (worse case scenario): \(O((V \log V + E))\)

• For large graphs where there is a path bewtween the starting vertex and ending vertex:

  • It is expected to terminate faster than pgr_dijkstra

Signatures

Summary

pgr_bdDijkstraCost(Edges SQL, from_vid,  to_vid  [, directed])
pgr_bdDijkstraCost(Edges SQL, from_vid,  to_vids [, directed])
pgr_bdDijkstraCost(Edges SQL, from_vids, to_vid  [, directed])
pgr_bdDijkstraCost(Edges SQL, from_vids, to_vids [, directed])
pgr_bdDijkstraCost(Edges SQL, Combinations SQL [, directed]) -- Proposed on v3.2

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Using default

pgr_bdDijkstraCost(Edges SQL, from_vid,  to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Example :

From vertex \(2\) to vertex \(3\) on a directed graph

SELECT * FROM pgr_bdDijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, 3
);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         5
(1 row)

pgr_bdDijkstraCost(Edges SQL, from_vid,  to_vid  [, directed])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

SELECT * FROM pgr_bdDijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, 3,
    false
);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         1
(1 row)

pgr_bdDijkstraCost(Edges SQL, from_vid,  to_vids [, directed])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

SELECT * FROM pgr_bdDijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, ARRAY[3, 11]);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         5
         2       11         3
(2 rows)

pgr_bdDijkstraCost(Edges SQL, from_vids, to_vids [, directed])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

SELECT * FROM pgr_bdDijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[2, 7], 3);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         5
         7        3         6
(2 rows)

pgr_bdDijkstraCost(Edges SQL, start_vids, end_vids [, directed])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

SELECT * FROM pgr_bdDijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[2, 7], ARRAY[3, 11]);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         5
         2       11         3
         7        3         6
         7       11         4
(4 rows)

pgr_bdDijkstra(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

SELECT * FROM pgr_bdDijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    'SELECT * FROM ( VALUES (2, 3), (7, 11) ) AS t(source, target)');
 start_vid  end_vid  agg_cost
-----------+---------+----------
         2        3         5
         7       11         4
(2 rows)

Parameters

Inner queries

Result Columns

Returns SET OF (start_vid, end_vid, agg_cost)

See Also

• The queries use the Sample Data network.

• pgr_bdDijkstra

• https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

• https://en.wikipedia.org/wiki/Bidirectional_search

Indices and tables

• Index

• Search Page