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.

_images/boost-inside.jpeg

Boost 图内部

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))\)

签名

总结

pgr_dagShortestPath(Edges SQL, start vid, end vid)
pgr_dagShortestPath(Edges SQL, start vid, end vids)
pgr_dagShortestPath(Edges SQL, start vids, end vid)
pgr_dagShortestPath(Edges SQL, start vids, end vids)
pgr_dagShortestPath(Edges SQL, Combinations SQL)
返回 (seq, path_seq, node, edge, cost, agg_cost) 的集合
OR EMPTY SET

一对一

pgr_dagShortestPath(Edges SQL, start vid, end vid)
返回 (seq, path_seq, node, edge, cost, agg_cost) 的集合
OR EMPTY SET
示例:

在 有向 图上，从顶点 \(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)

一对多

pgr_dagShortestPath(Edges SQL, start vid, end vids)
返回 (seq, path_seq, node, edge, cost, agg_cost) 的集合
OR EMPTY SET
示例:

从顶点 \(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)

多对一

pgr_dagShortestPath(Edges SQL, start vids, end vid)
返回 (seq, path_seq, node, edge, cost, agg_cost) 的集合
OR EMPTY SET
示例:

从顶点 \(\{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)

多对多

pgr_dagShortestPath(Edges SQL, start vids, end vids)
返回 (seq, path_seq, node, edge, cost, agg_cost) 的集合
OR EMPTY SET
示例:

在 无向 图上，从顶点 \(\{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)

组合

pgr_dagShortestPath(Edges SQL, Combinations SQL)
返回 (seq, path_seq, node, edge, cost, 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_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

TEXT

Edges SQL 如下所述

Combinations SQL

TEXT

Combinations SQL 如下所述

start vid

BIGINT

路径起始顶点的标识符。

start vids

ARRAY[BIGINT]

起始顶点的标识符数组。

end vid

BIGINT

路径结束顶点的标识符。

end vids

ARRAY[BIGINT]

结束顶点的标识符数组。

内部查询

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

返回列

返回 (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) 的集合

列

类型

描述

seq

INTEGER

从 1 开始的顺序值。

path_seq

INTEGER

路径中的相对位置。 路径开头的值为 1。

start_vid

BIGINT

起始顶点的标识符。 当查询中有多个起始向量时返回。

end_vid

BIGINT

结束顶点的标识符。 当查询中有多个结束顶点时返回。

node

BIGINT

从 start_vid 到 end_vid 路径中节点的标识符。

edge

BIGINT

用于从路径序列中的 node 到下一个节点的边的标识符。 -1 表示路径的最后一个节点。

cost

FLOAT

从使用 edge 的 node 遍历到路径序列中的下一个节点的成本。

agg_cost

FLOAT

从 start_vid 到 node 的总成本。

其他示例

示例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)

另请参阅

索引和表格