pgr_dagShortestPath - 实验¶
pgr_dagShortestPath
— Returns the shortest path for weighted directed
acyclic graphs(DAG).
In particular, the DAG shortest paths algorithm implemented by Boost.Graph.
Warning
可能服务器崩溃
这些功能可能会导致服务器崩溃
Warning
实验功能
它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分:
这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
名称可能会改变。
签名可能会改变。
功能可能会改变。
pgTap 测试可能丢失。
可能需要 c/c++编码。
可能缺乏文档。
文档(如果有)可能需要重写。
可能需要自动生成文档示例。
可能需要社区的大量反馈。
可能取决于 pgRouting 的拟议功能
可能依赖于 pgRouting 的已弃用函数
可用性
版本3.2.0
新的 实验 函数:
pgr_dagShortestPath(组合)
版本3.0.0
新 实验 函数
描述¶
有向无环图(DAG)的最短路径是一种图搜索算法,用于解决加权有向无环图的最短路径问题,找到从起始顶点(start_vid
)到结束顶点(end_vid
)的最短路径。
这个实现只能用于 有向 图,且没有循环,即有向无环图。
该算法依靠对 DAG 进行拓扑排序来对顶点进行线性排序,因此比 Dijkstra 或 Bellman-Ford 算法更有效率。
- 主要特点是:
该过程仅对加权有向无环图有效。 否则它会抛出警告。
当存在路径时返回值。
当起始顶点和结束顶点相同时,就没有路径。
agg_cost`中未包括的值`(v, v) 的成本为`0`
当起始顶点和结束顶点不同且不存在路径时:
agg_cost`中未包括的值 `(u, v)`是数学符号中的 :math:infty`
出于优化目的,start_vids`或 `end_vids 中的任何重复值都将被忽略。
返回值是有序的:
start_vid 升序
end_vid 升序
运行时间: \(O(| start\_vids | * (V + E))\)
签名¶
总结
(seq, path_seq, node, edge, cost, agg_cost)
的集合一对一¶
(seq, path_seq, node, edge, cost, agg_cost)
的集合- 示例:
在 有向 图上,从顶点 \(5\) 到顶点 \(11\)
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
5, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | 4 | 1 | 1
3 | 3 | 7 | 8 | 1 | 2
4 | 4 | 11 | -1 | 0 | 3
(4 rows)
一对多¶
(seq, path_seq, node, edge, cost, agg_cost)
的集合- 示例:
从顶点 \(5\) 到顶点 \(\{7, 11\}\)
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
5, ARRAY[7, 11]);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | 4 | 1 | 1
3 | 3 | 7 | -1 | 0 | 2
4 | 1 | 5 | 1 | 1 | 0
5 | 2 | 6 | 4 | 1 | 1
6 | 3 | 7 | 8 | 1 | 2
7 | 4 | 11 | -1 | 0 | 3
(7 rows)
多对一¶
(seq, path_seq, node, edge, cost, agg_cost)
的集合- 示例:
从顶点 \(\{5, 10\}\) 到顶点 \(11\)
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
ARRAY[5, 10], 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | 4 | 1 | 1
3 | 3 | 7 | 8 | 1 | 2
4 | 4 | 11 | -1 | 0 | 3
5 | 1 | 10 | 5 | 1 | 0
6 | 2 | 11 | -1 | 0 | 1
(6 rows)
多对多¶
(seq, path_seq, node, edge, cost, agg_cost)
的集合- 示例:
在 无向 图上,从顶点 \(\{5, 15\} ` 到顶点 :math:\){11, 17}`
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
ARRAY[5, 15], ARRAY[11, 17]);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | 4 | 1 | 1
3 | 3 | 7 | 8 | 1 | 2
4 | 4 | 11 | -1 | 0 | 3
5 | 1 | 5 | 1 | 1 | 0
6 | 2 | 6 | 4 | 1 | 1
7 | 3 | 7 | 8 | 1 | 2
8 | 4 | 11 | 9 | 1 | 3
9 | 5 | 16 | 15 | 1 | 4
10 | 6 | 17 | -1 | 0 | 5
11 | 1 | 15 | 16 | 1 | 0
12 | 2 | 16 | 15 | 1 | 1
13 | 3 | 17 | -1 | 0 | 2
(13 rows)
组合¶
(seq, path_seq, node, edge, cost, agg_cost)
的集合- 示例:
在 无向 图上使用组合表
组合表:
SELECT source, target FROM combinations;
source | target
--------+--------
5 | 6
5 | 10
6 | 5
6 | 15
6 | 14
(5 rows)
查询:
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
'SELECT source, target FROM combinations');
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | -1 | 0 | 1
(2 rows)
参数¶
列 |
类型 |
描述 |
---|---|---|
|
Edges SQL 如下所述 |
|
|
Combinations SQL 如下所述 |
|
start vid |
|
路径起始顶点的标识符。 |
start vids |
|
起始顶点的标识符数组。 |
end vid |
|
路径结束顶点的标识符。 |
end vids |
|
结束顶点的标识符数组。 |
内部查询¶
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。 |
|
|
起始顶点的标识符。 当查询中有多个起始向量时返回。 |
|
|
结束顶点的标识符。 当查询中有多个结束顶点时返回。 |
|
|
从 |
|
|
用于从路径序列中的 |
|
|
从使用 |
|
|
从 |
其他示例¶
- 示例1:
演示中重复的值被忽略,且结果被排序。
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
ARRAY[5, 10, 5, 10, 10, 5], ARRAY[11, 17, 17, 11]);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | 4 | 1 | 1
3 | 3 | 7 | 8 | 1 | 2
4 | 4 | 11 | -1 | 0 | 3
5 | 1 | 5 | 1 | 1 | 0
6 | 2 | 6 | 4 | 1 | 1
7 | 3 | 7 | 8 | 1 | 2
8 | 4 | 11 | 9 | 1 | 3
9 | 5 | 16 | 15 | 1 | 4
10 | 6 | 17 | -1 | 0 | 5
11 | 1 | 10 | 5 | 1 | 0
12 | 2 | 11 | -1 | 0 | 1
13 | 1 | 10 | 5 | 1 | 0
14 | 2 | 11 | 9 | 1 | 1
15 | 3 | 16 | 15 | 1 | 2
16 | 4 | 17 | -1 | 0 | 3
(16 rows)
- 示例2:
使 start_vids 与 end_vids 相同
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
ARRAY[5, 10, 11], ARRAY[5, 10, 11]);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 5 | 1 | 1 | 0
2 | 2 | 6 | 4 | 1 | 1
3 | 3 | 7 | 8 | 1 | 2
4 | 4 | 11 | -1 | 0 | 3
5 | 1 | 10 | 5 | 1 | 0
6 | 2 | 11 | -1 | 0 | 1
(6 rows)
- 示例3:
手动指定的顶点组合。
SELECT * FROM pgr_dagShortestPath(
'SELECT id, source, target, cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 6 | 4 | 1 | 0
2 | 2 | 7 | -1 | 0 | 1
(2 rows)
另请参阅¶
索引和表格