pgr_dijkstraNear - 拟议¶
pgr_dijkstraNear - 使用 Dijkstra 算法，找到通往最近顶点的路径。
Warning
下一版本的拟议功能。
它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分：
这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
名字可能不会改变。（但仍然有可能改变）
签名可能不会改变。（但仍然有可能改变）
功能可能不会改变。（但仍然有可能改变）
pgTap 测试已经完成。 但可能需要更多。
文档可能需要完善。
Boost 图内部¶
可用性
版本 3.3.0
升级至 拟议 函数
版本3.2.0
新 实验 函数
描述¶
给定一个图、一个起始顶点和一组终止顶点，该函数会找出从起始顶点到最近的终止顶点的最短路径。
特征¶
使用 Dijkstra 算法。
适用于 有向 和 无向 图。
当有多条路径通向同一顶点且成本相同时：
算法将只返回一条路径
可选择查找多条路径。
当需要返回多条路径时：
结果按以下顺序递增排序：
总成本
在总成本相同值范围内：
结果按 (source, target)排序
运行时间：Dijkstra 运行时间： \(drt = O((|E| + |V|)log|V|)\)
一对多； \(drt\)
多对一： \(drt\)
多对多： \(drt * |Starting vids|\)
组合： \(drt * |Starting vids|\)
签名¶
总结
[directed, cap][directed, cap, global](seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)一对多¶
[directed, cap](seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- 示例:
从顶点 \(6\) 乘车出发，找到最近的地铁站。
使用 有向 图进行汽车路线规划。
地铁站位于以下顶点上 \(\{1, 10, 11\}\)
使用的默认值：
directed => true
cap => 1
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 6, ARRAY[10, 11, 1]);
4 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
5-----+----------+-----------+---------+------+------+------+----------
6 1 | 1 | 6 | 11 | 6 | 4 | 1 | 0
7 2 | 2 | 6 | 11 | 7 | 8 | 1 | 1
8 3 | 3 | 6 | 11 | 11 | -1 | 0 | 2
9(3 rows)
10
结果显示，位于顶点 \(11\) 的站最近。
多对一¶
[directed, cap](seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- 示例:
从地铁站开车出发，找到距离顶点 \(2\) 最近的 两个 车站
使用 有向 图进行汽车路线规划。
地铁站位于以下顶点上 \(\{1, 10, 11\}\)
第 4 行：使用位置参数： directed 设置为`true`
第 5 行：使用命名参数 cap => 2
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 ARRAY[10, 11, 1], 6,
4 true,
5 cap => 2);
6 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
7-----+----------+-----------+---------+------+------+------+----------
8 1 | 1 | 10 | 6 | 10 | 2 | 1 | 0
9 2 | 2 | 10 | 6 | 6 | -1 | 0 | 1
10 3 | 1 | 11 | 6 | 11 | 8 | 1 | 0
11 4 | 2 | 11 | 6 | 7 | 4 | 1 | 1
12 5 | 3 | 11 | 6 | 6 | -1 | 0 | 2
13(5 rows)
14
结果显示，位于顶点 \(10\) 的站点最近，其次是 \(11\)。
多对多¶
[定向、上限、全局](seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- 示例:
在两条公交线路之间寻找最佳的行人通道
使用 无向 图进行行人路线规划
第一条地铁线的站点位于 \(\{15, 16\}\)
地铁二号线的站点是 \(\{1, 10, 11\}\)
第 4 行：使用命名参数：directed => false
使用的默认值：
cap => 1
global => true
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 ARRAY[15, 16], ARRAY[10, 11, 1],
4 directed => false);
5 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
6-----+----------+-----------+---------+------+------+------+----------
7 1 | 1 | 15 | 10 | 15 | 3 | 1 | 0
8 2 | 2 | 15 | 10 | 10 | -1 | 0 | 1
9(2 rows)
10
对于行人来说，上下车的最佳连接点是第一条地铁线的顶点 \(15\) 和第二条地铁线的顶点 \(10\)。
只返回 一条 路由，因为 global 为 true 且 cap 为 1
组合¶
[定向、上限、全局](seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)- 示例:
查找两条地铁线所有站点之间的最佳汽车连接线路
使用 有向 图进行汽车路线规划。
第一条地铁线的站点是 \(\{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
1SELECT * FROM pgr_dijkstraNear(
2 'SELECT id, source, target, cost, reverse_cost FROM edges',
3 'SELECT unnest(ARRAY[10, 11, 1]) as source, target
4 FROM (SELECT unnest(ARRAY[15, 16]) AS target) a
5 UNION
6 SELECT unnest(ARRAY[15, 16]), target
7 FROM (SELECT unnest(ARRAY[10, 11, 1]) AS target) b',
8 global => false);
9 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
10-----+----------+-----------+---------+------+------+------+----------
11 1 | 1 | 11 | 16 | 11 | 9 | 1 | 0
12 2 | 2 | 11 | 16 | 16 | -1 | 0 | 1
13 3 | 1 | 15 | 10 | 15 | 3 | 1 | 0
14 4 | 2 | 15 | 10 | 10 | -1 | 0 | 1
15 5 | 1 | 16 | 11 | 16 | 9 | 1 | 0
16 6 | 2 | 16 | 11 | 11 | -1 | 0 | 1
17 7 | 1 | 10 | 16 | 10 | 5 | 1 | 0
18 8 | 2 | 10 | 16 | 11 | 9 | 1 | 1
19 9 | 3 | 10 | 16 | 16 | -1 | 0 | 2
20 10 | 1 | 1 | 16 | 1 | 6 | 1 | 0
21 11 | 2 | 1 | 16 | 3 | 7 | 1 | 1
22 12 | 3 | 1 | 16 | 7 | 8 | 1 | 2
23 13 | 4 | 1 | 16 | 11 | 9 | 1 | 3
24 14 | 5 | 1 | 16 | 16 | -1 | 0 | 4
25(14 rows)
26
从结果来看：
将第一条地铁线 \({1, 10, 11\}\) 连接到第二条地铁线 \({15, 16\}\)：
从第一条线路的所有站点出发的最佳连接是： \({(1 \rightarrow 16) (10 \rightarrow 16) (11 \rightarrow 16)}\)
最好的方法是 \((11/rightarrow 16)\)，成本是 \(1\) （行：11 和`12`）
将第二条地铁线 \({15, 16\}\) 连接到第一条地铁线 \({1, 10, 11\}\)：
从二号线所有站点出发的最佳连接是： \({(15 ／rightarrow 10) (16 ／rightarrow 11)}\)
它们都一样好，因为它们具有相同的成本（线路：13 和`14`以及线路：15 和`16`）
参数¶
列 |
类型 |
描述 |
|---|---|---|
|
Edges SQL 如下所述 |
|
|
Combinations SQL 如下所述 |
|
start vid |
|
路径起始顶点的标识符。 |
start vids |
|
起始顶点的标识符数组。 |
end vid |
|
路径结束顶点的标识符。 |
end vids |
|
结束顶点的标识符数组。 |
Dijkstra 可选参数¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
|
|
|
接近可选参数¶
参数 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
|
|
查找最多 |
|
|
|
|
内部查询¶
Edges SQL¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
ANY-INTEGER |
边的标识符。 |
|
|
ANY-INTEGER |
边的第一个端点顶点的标识符。 |
|
|
ANY-INTEGER |
边的第二个端点顶点的标识符。 |
|
|
ANY-NUMERICAL |
边( |
|
|
ANY-NUMERICAL |
-1 |
边(
|
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
分量 SQL¶
参数 |
类型 |
描述 |
|---|---|---|
|
ANY-INTEGER |
出发顶点的标识符。 |
|
ANY-INTEGER |
到达顶点的标识符。 |
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT
结果列¶
返回 (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
列 |
类型 |
描述 |
|---|---|---|
|
|
从 1 开始的顺序值。 |
|
|
路径中的相对位置。 路径开头的值为 1。 |
|
|
当前路径起始顶点的标识符。 |
|
|
当前路径结束顶点的标识符。 |
|
|
从 |
|
|
用于从路径序列中的 |
|
|
从使用 |
|
|
从 |
另请参阅¶
索引和表格