`pgr_bdDijkstraCostMatrix`¶

pgr_bdDijkstraCostMatrix - 使用 pgr_bdDijkstra 计算成本矩阵。

可用性

版本3.0.0
- 官方函数
版本2.5.0
- 新拟议函数

描述¶

使用双向Dijkstra算法，计算并返回成本矩阵。

仅在具有正成本的边进行处理。
- 成本列上的负值被解释为边不存在。
当存在路径时返回值。
当没有路径时：
- 当起始顶点和结束顶点相同时。
  - 未包含值 \((v, v)\) 的 aggregate cost 为 \(0\)
- 当起始顶点和结束顶点不同且不存在路径时：
  - 未包含值 \((u, v)\) 的 aggregate cost 是 \(\infty\)
出于优化目的，起始顶点或结束顶点中的任何重复值都将被忽略。
运行时间（最坏情况）： \(O((V \log V + E))\)
对于起始顶点和结束顶点之间存在路径的大型图:
- 预计终止速度比 pgr_dijkstra 更快

主要特点是：

可用作 pgr_TSP 的输入。
- 当得到的矩阵是对称且没有 \(\infty\) 值时直接使用。
- 用户有责任使矩阵对称。
  - 通过使用非对称值的几何平均或调和平均。
  - 通过使用 max 或 min 非对称值。
  - 通过将上三角形设置为下三角形的镜像。
  - 通过将下三角形设置为上三角形的镜像。
- 确定 \(\infty\) 值也是用户的责任。
每个函数都是其所属家族的一部分。
它不返回路径。
返回图中节点对组合的最短路径的成本总和。
仅在具有正成本的边进行处理。
当存在路径时返回值。
- 当起始顶点和结束顶点相同时，就没有路径。
  - 未包含值 (v, v) 中的总成本为 0。
- 当起始顶点和结束顶点不同且不存在路径时。
  - 未包含值 (u, v) 中的总成本为 \(\infty\) 。
假设返回的值存储在表中：
- 唯一索引将是一对： (start_vid, end_vid)。
根据函数及其参数，结果可能是对称的。
- (u, v) 的总成本与 (v, u) 相同。
start vids 中的任何重复值都会被忽略。
返回值是有序的：
- start_vid 升序
- end_vid 升序

签名¶

总结

pgr_bdDijkstraCostMatrix(Edges SQL, start vids, [directed])

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

OR EMPTY SET

示例:: 在一个无向图上的顶点集合 \(\{5, 6, 10, 15\}\) 的对称成本矩阵

SELECT * FROM pgr_bdDijkstraCostMatrix(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  (SELECT array_agg(id)
    FROM vertices
    WHERE id IN (5, 6, 10, 15)),
  false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         5 |       6 |        1
         5 |      10 |        2
         5 |      15 |        3
         6 |       5 |        1
         6 |      10 |        1
         6 |      15 |        2
        10 |       5 |        2
        10 |       6 |        1
        10 |      15 |        1
        15 |       5 |        3
        15 |       6 |        2
        15 |      10 |        1
(12 rows)

参数¶

列	类型	描述
Edges SQL	`TEXT`	Edges SQL 如下所述
start 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

结果列¶

(start_vid, end_vid, agg_cost) 的集合

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

其他示例¶

示例:: 与 pgr_TSP 一起使用。

SELECT * FROM pgr_TSP(
  $$
  SELECT * FROM pgr_bdDijkstraCostMatrix(
    'SELECT id, source, target, cost, reverse_cost FROM edges',
    (SELECT array_agg(id)
      FROM vertices
      WHERE id IN (5, 6, 10, 15)),
    false)
  $$);
NOTICE:  pgr_TSP no longer solving with simulated annaeling
HINT:  Ignoring annaeling parameters
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    5 |    0 |        0
   2 |    6 |    1 |        1
   3 |   10 |    1 |        2
   4 |   15 |    1 |        3
   5 |    5 |    3 |        6
(5 rows)

另请参阅¶

索引和表格

pgr_bdDijkstraCostMatrix¶

描述¶

签名¶

参数¶

可选参数¶

内部查询¶

Edges SQL¶

结果列¶

其他示例¶

另请参阅¶

`pgr_bdDijkstraCostMatrix`¶