pgr_bdDijkstraCost

pgr_bdDijkstraCost — Returns the shortest path's cost using Bidirectional Dijkstra algorithm.

Boost 图内部

可用性

• 版本3.2.0

  • 新 拟议 的签名：

    • pgr_bdDijkstraCost (组合)

• 版本3.0.0

  • 官方 函数

• 版本2.5.0

  • 新 拟议 函数

描述

pgr_bdDijkstraCost 函数使用双向 Dijkstra 算法汇总最短路径的成本。

• 仅在具有正成本的边进行处理。

  • 成本列上的负值被解释为边不存在。

• 当存在路径时返回值。

• 当没有路径时：

  • 当起始顶点和结束顶点相同时。

    • 未包含值 \((v, v)\) 的 aggregate cost 为 \(0\)

  • 当起始顶点和结束顶点不同且不存在路径时：

    • 未包含值 \((u, v)\) 的 aggregate cost 是 \(\infty\)

• 出于优化目的，起始顶点或结束顶点中的任何重复值都将被忽略。

• 运行时间（最坏情况）： \(O((V \log V + E))\)

• 对于起始顶点和结束顶点之间存在路径的大型图:

  • 预计终止速度比 pgr_dijkstra 更快

• 它不返回路径。

• 返回所请求的每对节点组合的最短路径的成本总和。

• 假设返回的值存储在表中，因此唯一索引将是一对： (start_vid, end_vid)。

• 根据函数及其参数，结果可能是对称的。

  • \((u, v)\) 的 总成本 与 \((v, u)\) 的相同。

• 起始或结束顶点标识符中的任何重复值都将被忽略。

• 返回值是有序的：

  • start_vid 升序

  • end_vid 升序

签名

总结

pgr_bdDijkstraCost(Edges SQL, start vid, end vid , [directed])

pgr_bdDijkstraCost(Edges SQL, start vid, end vids, [directed])

pgr_bdDijkstraCost(Edges SQL, start vids, end vid , [directed])

pgr_bdDijkstraCost(Edges SQL, start vids, end vids, [directed])

pgr_bdDijkstraCost(Edges SQL, Combinations SQL, [ directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

一对一

pgr_bdDijkstraCost(Edges SQL, start vid, end vid , [directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:

在 有向 图上从顶点 \(6\) 到顶点 \(10\)

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)

一对多

pgr_bdDijkstraCost(Edges SQL, start vid, end vids, [directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:

在 有向 图上从顶点 \(6\) 到顶点 \(\{10, 17\}\)

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)

多对一

pgr_bdDijkstraCost(Edges SQL, start vids, end vid , [directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:

在 有向 图上从顶点 \(\{6, 1\}\) 到顶点 \(17\)

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)

多对多

pgr_bdDijkstraCost(Edges SQL, start vids, end vids, [directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:

在 无向 图上从顶点 \(\{6, 1\}\) 到顶点 \(\{10, 17\}\)

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)

组合

pgr_bdDijkstraCost(Edges SQL, Combinations SQL, [directed])

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:

在 无向 图上使用组合表

组合表：

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)

参数

列	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述
Combinations SQL	TEXT	Combinations SQL 如下所述
start vid	BIGINT	路径起始顶点的标识符。
start vids	ARRAY[BIGINT]	起始顶点的标识符数组。
end vid	BIGINT	路径结束顶点的标识符。
end vids	ARRAY[BIGINT]	结束顶点的标识符数组。

可选参数

列	类型	默认	描述
directed	BOOLEAN	true	当 true 时，该图被视为有 有向 如果为 false ，则该图被视为 无向。

内部查询

Edges SQL

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		边(source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

分量 SQL

参数	类型	描述
source	ANY-INTEGER	出发顶点的标识符。
target	ANY-INTEGER	到达顶点的标识符。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

结果列

(start_vid, end_vid, agg_cost) 的集合

列	类型	描述
start_vid	BIGINT	起始顶点的标识符。
end_vid	BIGINT	结束顶点的标识符。
agg_cost	FLOAT	从 start_vid 到 end_vid 的总成本。

其他示例

示例1:

演示中重复的值被忽略，且结果被排序。

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)

示例2:

使 start vids 与 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)

示例3:

手动指定的顶点组合。

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)

另请参阅

• 双向 Dijkstra - 函数族

• 示例数据

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

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

索引和表格

• Index

• Search Page