pgr_bdDijkstraCost - pgRouting Manual (3.3)

Description

The pgr_bdDijkstraCost function sumarizes of the cost of the shortest path using the bidirectional Dijkstra Algorithm.

• Process is done only on edges with positive costs.

  • A negative value on a cost column is interpreted as the edge does not exist.

• Values are returned when there is a path.

• When there is no path:

  • When the starting vertex and ending vertex are the same.

    • The aggregate cost of the non included values \((v, v)\) is \(0\)

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

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

• For optimization purposes, any duplicated value in the starting vertices or on the ending vertices are ignored.

• 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

• It does not return a path.

• Returns the sum of the costs of the shortest path of each pair combination of nodes requested.

• Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid) .

• Depending on the function and its parameters, the results can be symmetric.

  • The aggregate cost of \((u, v)\) is the same as for \((v, u)\) .

• Any duplicated value in the start or end vertex identifiers are ignored.

• The returned values are ordered:

  • start_vid ascending

  • end_vid ascending

Signatures

Summary

SELECT * FROM pgr_bdDijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  6, 10, true);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         6       10         5
(1 row)

SELECT * FROM pgr_bdDijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  6, ARRAY[10, 17]);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         6       10         5
         6       17         4
(2 rows)

SELECT * FROM pgr_bdDijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[6, 1], 17);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         1       17         5
         6       17         4
(2 rows)

SELECT * FROM pgr_bdDijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[6, 1], ARRAY[10, 17],
  directed => false);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         1       10         4
         1       17         5
         6       10         1
         6       17         4
(4 rows)

SELECT source, target FROM combinations;
 source  target
--------+--------
      5       6
      5      10
      6       5
      6      15
      6      14
(5 rows)

SELECT * FROM pgr_bdDijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  'SELECT source, target FROM combinations',
  false);
 start_vid  end_vid  agg_cost
-----------+---------+----------
         5        6         1
         5       10         2
         6        5         1
         6       15         2
(4 rows)

Parameters

Inner Queries

Result Columns

Set of (start_vid, end_vid, agg_cost)

Additional Examples

Example 1 :

Demonstration of repeated values are ignored, and result is sorted.

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

Example 2 :

Making start vids the same as end vids .

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

Example 3 :

Manually assigned vertex combinations.

SELECT * FROM pgr_bdDijkstraCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
 start_vid  end_vid  agg_cost
-----------+---------+----------
         6        7         1
         6       10         5
        12       10         4
(3 rows)

See Also

• Bidirectional Dijkstra - Family of functions

• Sample Data

• 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