`pgr_dijkstraNearCost` - 拟议¶

pgr_dijkstraNearCost` - 使用 dijkstra 算法，找到通往最近顶点的路径。

Warning

下一版本的拟议功能。

它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分：
- 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名字可能不会改变。（但仍然有可能改变）
- 签名可能不会改变。（但仍然有可能改变）
- 功能可能不会改变。（但仍然有可能改变）
- pgTap 测试已经完成。但可能需要更多。
- 文档可能需要完善。

可用性

版本 3.3.0
- 升级至拟议函数
版本3.2.0
- 新实验函数

描述¶

给定一个图、一个起始顶点和一组终止顶点，该函数会找出从起始顶点到最近的终止顶点的最短路径。

特征¶

使用 Dijkstra 算法。
适用于有向和无向图。
当有多条路径通向同一顶点且成本相同时：
- 算法将只返回一条路径
可选择查找多条路径。
- 当需要返回多条路径时：
  - 结果按以下顺序递增排序：
    - 总成本
    - 在总成本相同值范围内：
      - 结果按 (source, target)排序
运行时间：Dijkstra 运行时间： \(drt = O((|E| + |V|)log|V|)\)
- 一对多； \(drt\)
- 多对一： \(drt\)
- 多对多： \(drt * |Starting vids|\)
- 组合： \(drt * |Starting vids|\)

签名¶

总结

pgr_dijkstraNearCost(Edges SQL, start vid, end vids, [options A])
pgr_dijkstraNearCost(Edges SQL, start vids, end vid, [options A])
pgr_dijkstraNearCost(Edges SQL, start vids, end vids, [options B])
pgr_dijkstraNearCost(Edges SQL, Combinations SQL, [options B])
选项A： [directed, cap]
选项B： [directed, cap, global]

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

OR EMPTY SET

一对多¶

pgr_dijkstraNearCost(Edges SQL, start vid, end vids, [options])

选项： [directed, cap]

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

OR EMPTY SET

示例:: 从顶点 \(6\) 乘车出发，找到最近的地铁站。

使用有向图进行汽车路线规划。
地铁站位于以下顶点上 \(\{1, 10, 11\}\)
使用的默认值：
- directed => true
- cap => 1

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  6, ARRAY[10, 11, 1]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      11 |        2
(1 row)

结果显示，位于顶点 \(11\) 的站最近。

多对一¶

pgr_dijkstraNearCost(Edges SQL, start vid, end vid, [options])

选项： [directed, cap]

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

OR EMPTY SET

示例:: 从地铁站开车出发找到距离顶点 \(6\) 最近的两个车站

使用有向图进行汽车路线规划。
地铁站位于以下顶点上 \(\{1, 10, 11\}\)
第 4 行：使用位置参数： directed 设置为`true`
第 5 行：使用命名参数 cap => 2

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[10, 11, 1], 6,
  true,
  cap => 2) ORDER BY agg_cost;
 start_vid | end_vid | agg_cost
-----------+---------+----------
        10 |       6 |        1
        11 |       6 |        2
(2 rows)

结果显示，位于顶点 \(10\) 的站点最近，其次是 \(11\)。

多对多¶

pgr_dijkstraNearCost(Edges SQL, start vids, end vids, [options])

选项： [定向、上限、全局]

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

OR EMPTY SET

示例:: 在两条公交线路之间寻找最佳的行人通道

使用无向图进行行人路线规划
第一条地铁线的站点位于 \(\{15, 16\}\)
地铁二号线的站点是 \(\{1, 10, 11\}\)
第 4 行：使用命名参数：directed => false
使用的默认值：
- cap => 1
- global => true

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[15, 16], ARRAY[10, 11, 1],
  directed => false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
        15 |      10 |        1
(1 row)

对于行人来说，上下车的最佳连接点是第一条地铁线的顶点 \(15\) 和第二条地铁线的顶点 \(10\)。

只返回一条路由，因为 global 为 true 且 cap 为 1

组合¶

pgr_dijkstraNearCost(Edges SQL, Combinations SQL, [options])

选项： [定向、上限、全局]

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

OR EMPTY SET

示例:: 查找两条地铁线所有站点之间的最佳汽车连接线路

使用有向图进行汽车路线规划。
第一条地铁线的站点是 \(\{1, 10, 11\}\)
地铁二号线站点位于 \(\{15, 16\}\)

组合内容：

SELECT unnest(ARRAY[10, 11, 1]) as source, target
FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
  UNION
SELECT unnest(ARRAY[15, 16]), target
FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b ORDER BY source, target;
 source | target
--------+--------
      1 |     15
      1 |     16
     10 |     15
     10 |     16
     11 |     15
     11 |     16
     15 |      1
     15 |     10
     15 |     11
     16 |      1
     16 |     10
     16 |     11
(12 rows)

查询：

行 3~4 设置地铁三号线的起始顶点和地铁二号线的终点顶点
行 6~7 将起始顶点设置为第一条地铁线上的顶点，将终点顶点设置为第一条地铁线上的顶点
第 8 行：使用名为 global => false 的参数
使用的默认值：
- directed => true
- cap => 1

SELECT * FROM pgr_dijkstraNearCost(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  'SELECT unnest(ARRAY[10, 11, 1]) as source, target
   FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
     UNION
   SELECT unnest(ARRAY[15, 16]), target
   FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b',
  global => false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
        11 |      16 |        1
        15 |      10 |        1
        16 |      11 |        1
        10 |      16 |        2
         1 |      16 |        4
(5 rows)

从结果来看：

将第一条地铁线 \({1, 10, 11\}\) 连接到第二条地铁线 \({15, 16\}\)：
- 从第一条线路的所有站点出发的最佳连接是： \({(1 \rightarrow 16) (10 \rightarrow 16) (11 \rightarrow 16)}\)
- 最好的方法是 \((11/rightarrow 16)\)，成本是 \(1\) (lines: 1)
将第二条地铁线 \({15, 16\}\) 连接到第一条地铁线 \({1, 10, 11\}\)：
- 从二号线所有站点出发的最佳连接是： \({(15 ／rightarrow 10) (16 ／rightarrow 11)}\)
- 由于成本相同，所以两者同样好。(线路：12 和 13）

参数¶

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

Dijkstra 可选参数¶

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

接近可选参数¶

参数	类型	默认	描述
`cap`	`BIGINT`	`1`	查找最多 `cap` 条最近的最短路径
`global`	`BOOLEAN`	`true`	`true` 时：仅返回 `cap` 结果当 `false` 时：将返回每个 `Start vid` 的 `cap` 限值

内部查询¶

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` 的总成本。

另请参阅¶

Dijkstra - 函数族
pgr_dijkstraNear - 拟议
示例数据网络。
boost: https://www.boost.org/libs/graph/doc/table_of_contents.html
维基百科：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

索引和表格

pgr_dijkstraNearCost - 拟议¶

描述¶

特征¶

签名¶

一对多¶

多对一¶

多对多¶

组合¶

参数¶

Dijkstra 可选参数¶

接近可选参数¶

内部查询¶

Edges SQL¶

分量 SQL¶

结果列¶

另请参阅¶

`pgr_dijkstraNearCost` - 拟议¶