pgr_dijkstra`¶
pgr_dijkstra — Shortest path using Dijkstra algorithm.
Boost 图内部¶
可用性
版本 3.5.0
版本 3.1.0
新 拟议 函数：
pgr_dijkstra(组合)
版本3.0.0
官方 函数
版本 2.2.0
版本2.1.0
pgr_dijkstra(一对一)的签名更改
版本2.0.0
官方
pgr_dijkstra(一对一)
描述¶
Dijkstra算法，由荷兰计算机科学家Edsger Dijkstra于1956年提出。它是一种图搜索算法，解决具有非负边路径成本的图的最短路径问题，产生从起始顶点到结束顶点的最短路径。 该实现可以与有向图和无向图一起使用。
仅在具有正成本的边进行处理。
成本列上的负值被解释为边不存在。
当存在路径时返回值。
当没有路径时：
当起始顶点和结束顶点相同时。
未包含值 \((v, v)\) 的 aggregate cost 为 \(0\)
当起始顶点和结束顶点不同且不存在路径时：
未包含值 \((u, v)\) 的 aggregate cost 是 \(\infty\)
出于优化目的，起始顶点或结束顶点中的任何重复值都将被忽略。
运行时间： \(O(| start\ vids | * (V \log V + E))\)
签名¶
总结
pgr_dijkstra(Edges SQL, start vid, end vid, [
directed])pgr_dijkstra(Edges SQL, start vid, end vids, [
directed])pgr_dijkstra(Edges SQL, start vid, end vid, [
directed])pgr_dijkstra(Edges SQL, start vids, end vids, [
directed])Returns set of
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
一对一¶
pgr_dijkstra(Edges SQL, start vid, end vid, [
directed])Returns set of
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在 有向 图上从顶点 \(6\) 到顶点 \(10\)
SELECT * FROM pgr_Dijkstra(
'select id, source, target, cost, reverse_cost from edges',
6, 10, true);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
一对多¶
pgr_dijkstra(Edges SQL, start vid, end vids, [
directed])Returns set of
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在 有向 图上，从顶点 \(6\) 到顶点 \(\{10, 17\}\)
SELECT * FROM pgr_Dijkstra(
'select id, source, target, cost, reverse_cost from edges',
6, ARRAY[10, 17]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 1 | 6 | 17 | 6 | 4 | 1 | 0
8 | 2 | 6 | 17 | 7 | 8 | 1 | 1
9 | 3 | 6 | 17 | 11 | 9 | 1 | 2
10 | 4 | 6 | 17 | 16 | 15 | 1 | 3
11 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(11 rows)
多对一¶
pgr_dijkstra(Edges SQL, start vid, end vid, [
directed])Returns set of
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在 有向 图上从顶点 \(\{6, 1\}\) 到顶点 \(17\)
SELECT * FROM pgr_Dijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
3 | 3 | 1 | 17 | 7 | 8 | 1 | 2
4 | 4 | 1 | 17 | 11 | 11 | 1 | 3
5 | 5 | 1 | 17 | 12 | 13 | 1 | 4
6 | 6 | 1 | 17 | 17 | -1 | 0 | 5
7 | 1 | 6 | 17 | 6 | 4 | 1 | 0
8 | 2 | 6 | 17 | 7 | 8 | 1 | 1
9 | 3 | 6 | 17 | 11 | 11 | 1 | 2
10 | 4 | 6 | 17 | 12 | 13 | 1 | 3
11 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(11 rows)
多对多¶
pgr_dijkstra(Edges SQL, start vids, end vids, [
directed])Returns set of
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在 无向 图上从顶点 \(\{6, 1\}\) 到顶点 \(\{10, 17\}\)
SELECT * FROM pgr_Dijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17],
directed => false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 3 | 1 | 10 | 7 | 4 | 1 | 2
4 | 4 | 1 | 10 | 6 | 2 | 1 | 3
5 | 5 | 1 | 10 | 10 | -1 | 0 | 4
6 | 1 | 1 | 17 | 1 | 6 | 1 | 0
7 | 2 | 1 | 17 | 3 | 7 | 1 | 1
8 | 3 | 1 | 17 | 7 | 8 | 1 | 2
9 | 4 | 1 | 17 | 11 | 9 | 1 | 3
10 | 5 | 1 | 17 | 16 | 15 | 1 | 4
11 | 6 | 1 | 17 | 17 | -1 | 0 | 5
12 | 1 | 6 | 10 | 6 | 2 | 1 | 0
13 | 2 | 6 | 10 | 10 | -1 | 0 | 1
14 | 1 | 6 | 17 | 6 | 4 | 1 | 0
15 | 2 | 6 | 17 | 7 | 8 | 1 | 1
16 | 3 | 6 | 17 | 11 | 11 | 1 | 2
17 | 4 | 6 | 17 | 12 | 13 | 1 | 3
18 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(18 rows)
组合¶
Returns set of
(seq, path_seq, start_vid, end_vid, 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_Dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations',
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 5 | 10 | 6 | 2 | 1 | 1
5 | 3 | 5 | 10 | 10 | -1 | 0 | 2
6 | 1 | 6 | 5 | 6 | 1 | 1 | 0
7 | 2 | 6 | 5 | 5 | -1 | 0 | 1
8 | 1 | 6 | 15 | 6 | 2 | 1 | 0
9 | 2 | 6 | 15 | 10 | 3 | 1 | 1
10 | 3 | 6 | 15 | 15 | -1 | 0 | 2
(10 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。 |
|
|
起始顶点的标识符。 当查询中有多个起始向量时返回。 |
|
|
结束顶点的标识符。 当查询中有多个结束顶点时返回。 |
|
|
从 |
|
|
用于从路径序列中的 |
|
|
从使用 |
|
|
从 |
其他示例¶
- 示例:
演示中重复的值被忽略，且结果被排序。
SELECT * FROM pgr_Dijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 10 | 7 | 8 | 1 | 0
2 | 2 | 7 | 10 | 11 | 9 | 1 | 1
3 | 3 | 7 | 10 | 16 | 16 | 1 | 2
4 | 4 | 7 | 10 | 15 | 3 | 1 | 3
5 | 5 | 7 | 10 | 10 | -1 | 0 | 4
6 | 1 | 7 | 15 | 7 | 8 | 1 | 0
7 | 2 | 7 | 15 | 11 | 9 | 1 | 1
8 | 3 | 7 | 15 | 16 | 16 | 1 | 2
9 | 4 | 7 | 15 | 15 | -1 | 0 | 3
10 | 1 | 10 | 7 | 10 | 5 | 1 | 0
11 | 2 | 10 | 7 | 11 | 8 | 1 | 1
12 | 3 | 10 | 7 | 7 | -1 | 0 | 2
13 | 1 | 10 | 15 | 10 | 5 | 1 | 0
14 | 2 | 10 | 15 | 11 | 9 | 1 | 1
15 | 3 | 10 | 15 | 16 | 16 | 1 | 2
16 | 4 | 10 | 15 | 15 | -1 | 0 | 3
17 | 1 | 15 | 7 | 15 | 16 | 1 | 0
18 | 2 | 15 | 7 | 16 | 9 | 1 | 1
19 | 3 | 15 | 7 | 11 | 8 | 1 | 2
20 | 4 | 15 | 7 | 7 | -1 | 0 | 3
21 | 1 | 15 | 10 | 15 | 3 | 1 | 0
22 | 2 | 15 | 10 | 10 | -1 | 0 | 1
(22 rows)
- 示例2:
使 start_vids 与 end_vids 相同
SELECT * FROM pgr_Dijkstra(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 10 | 7 | 8 | 1 | 0
2 | 2 | 7 | 10 | 11 | 9 | 1 | 1
3 | 3 | 7 | 10 | 16 | 16 | 1 | 2
4 | 4 | 7 | 10 | 15 | 3 | 1 | 3
5 | 5 | 7 | 10 | 10 | -1 | 0 | 4
6 | 1 | 7 | 15 | 7 | 8 | 1 | 0
7 | 2 | 7 | 15 | 11 | 9 | 1 | 1
8 | 3 | 7 | 15 | 16 | 16 | 1 | 2
9 | 4 | 7 | 15 | 15 | -1 | 0 | 3
10 | 1 | 10 | 7 | 10 | 5 | 1 | 0
11 | 2 | 10 | 7 | 11 | 8 | 1 | 1
12 | 3 | 10 | 7 | 7 | -1 | 0 | 2
13 | 1 | 10 | 15 | 10 | 5 | 1 | 0
14 | 2 | 10 | 15 | 11 | 9 | 1 | 1
15 | 3 | 10 | 15 | 16 | 16 | 1 | 2
16 | 4 | 10 | 15 | 15 | -1 | 0 | 3
17 | 1 | 15 | 7 | 15 | 16 | 1 | 0
18 | 2 | 15 | 7 | 16 | 9 | 1 | 1
19 | 3 | 15 | 7 | 11 | 8 | 1 | 2
20 | 4 | 15 | 7 | 7 | -1 | 0 | 3
21 | 1 | 15 | 10 | 15 | 3 | 1 | 0
22 | 2 | 15 | 10 | 10 | -1 | 0 | 1
(22 rows)
- 示例:
手动指定的顶点组合。
SELECT * FROM pgr_Dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
9 | 1 | 12 | 10 | 12 | 13 | 1 | 0
10 | 2 | 12 | 10 | 17 | 15 | 1 | 1
11 | 3 | 12 | 10 | 16 | 16 | 1 | 2
12 | 4 | 12 | 10 | 15 | 3 | 1 | 3
13 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(13 rows)
本节的示例基于 示例数据 网络。
对于带有 cost 和 reverse_cost 列的 有向 图¶
带成本列和反向成本列的有向图¶
1) 从 \(6\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
2) 从 \(6\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 7
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
3) 从 \(12\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
12, 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 12 | 10 | 12 | 13 | 1 | 0
2 | 2 | 12 | 10 | 17 | 15 | 1 | 1
3 | 3 | 12 | 10 | 16 | 16 | 1 | 2
4 | 4 | 12 | 10 | 15 | 3 | 1 | 3
5 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(5 rows)
4) 从 \(12\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
12, 7
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 12 | 7 | 12 | 13 | 1 | 0
2 | 2 | 12 | 7 | 17 | 15 | 1 | 1
3 | 3 | 12 | 7 | 16 | 9 | 1 | 2
4 | 4 | 12 | 7 | 11 | 8 | 1 | 3
5 | 5 | 12 | 7 | 7 | -1 | 0 | 4
(5 rows)
5) 使用 一对多 来获取示例1和示例2的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, ARRAY[10, 7]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(8 rows)
6) 使用 多对一 来获取示例2和示例4的解决方案¶
路径 \(\{6, 12\}\rightarrow\{7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 12], 7
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 12 | 7 | 12 | 13 | 1 | 0
4 | 2 | 12 | 7 | 17 | 15 | 1 | 1
5 | 3 | 12 | 7 | 16 | 9 | 1 | 2
6 | 4 | 12 | 7 | 11 | 8 | 1 | 3
7 | 5 | 12 | 7 | 7 | -1 | 0 | 4
(7 rows)
7) 使用 多对多 来获取示例1到4的解决方案¶
路径 \(\{6, 12\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 12], ARRAY[10,7]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
9 | 1 | 12 | 7 | 12 | 13 | 1 | 0
10 | 2 | 12 | 7 | 17 | 15 | 1 | 1
11 | 3 | 12 | 7 | 16 | 9 | 1 | 2
12 | 4 | 12 | 7 | 11 | 8 | 1 | 3
13 | 5 | 12 | 7 | 7 | -1 | 0 | 4
14 | 1 | 12 | 10 | 12 | 13 | 1 | 0
15 | 2 | 12 | 10 | 17 | 15 | 1 | 1
16 | 3 | 12 | 10 | 16 | 16 | 1 | 2
17 | 4 | 12 | 10 | 15 | 3 | 1 | 3
18 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(18 rows)
8) 使用 组合 来获取示例1到3的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\cup\{12\}\rightarrow\{10\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)'
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
9 | 1 | 12 | 10 | 12 | 13 | 1 | 0
10 | 2 | 12 | 10 | 17 | 15 | 1 | 1
11 | 3 | 12 | 10 | 16 | 16 | 1 | 2
12 | 4 | 12 | 10 | 15 | 3 | 1 | 3
13 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(13 rows)
对于带有 cost 和 reverse_cost 列的 无向 图¶
带成本列和反向成本列的无向图¶
9)从 \(6\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 10,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 2 | 1 | 0
2 | 2 | 6 | 10 | 10 | -1 | 0 | 1
(2 rows)
10) 从 \(6\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 7,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
11)从 \(12\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
12, 10,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 12 | 10 | 12 | 11 | 1 | 0
2 | 2 | 12 | 10 | 11 | 5 | 1 | 1
3 | 3 | 12 | 10 | 10 | -1 | 0 | 2
(3 rows)
12)从 \(12\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
12, 7,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 12 | 7 | 12 | 12 | 1 | 0
2 | 2 | 12 | 7 | 8 | 10 | 1 | 1
3 | 3 | 12 | 7 | 7 | -1 | 0 | 2
(3 rows)
13) 使用 一对多 来获取示例9和10的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, ARRAY[10,7],
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 2 | 1 | 0
4 | 2 | 6 | 10 | 10 | -1 | 0 | 1
(4 rows)
14) 使用 多对一 来获取示例10和12的解决方案¶
路径 \(\{6, 12\}\rightarrow\{7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6,12], 7,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 12 | 7 | 12 | 12 | 1 | 0
4 | 2 | 12 | 7 | 8 | 10 | 1 | 1
5 | 3 | 12 | 7 | 7 | -1 | 0 | 2
(5 rows)
15) 使用 多对多 来获取示例9到12的解决方案¶
路径 \(\{6, 12\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 12], ARRAY[10,7],
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 2 | 1 | 0
4 | 2 | 6 | 10 | 10 | -1 | 0 | 1
5 | 1 | 12 | 7 | 12 | 12 | 1 | 0
6 | 2 | 12 | 7 | 8 | 10 | 1 | 1
7 | 3 | 12 | 7 | 7 | -1 | 0 | 2
8 | 1 | 12 | 10 | 12 | 11 | 1 | 0
9 | 2 | 12 | 10 | 11 | 5 | 1 | 1
10 | 3 | 12 | 10 | 10 | -1 | 0 | 2
(10 rows)
16) 使用 组合 来获取示例9到11的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\cup\{12\}\rightarrow\{10\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)',
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 2 | 1 | 0
4 | 2 | 6 | 10 | 10 | -1 | 0 | 1
5 | 1 | 12 | 10 | 12 | 11 | 1 | 0
6 | 2 | 12 | 10 | 11 | 5 | 1 | 1
7 | 3 | 12 | 10 | 10 | -1 | 0 | 2
(7 rows)
仅适用于 有向 图，且仅包含 cost 列¶
仅有成本列的有向图¶
17)从 \(6\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
6, 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)
18) 从 \(6\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
6, 7
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
19)从 \(12\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
12, 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)
20) 从 \(12\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
12, 7
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)
21) 使用 一对多 来获取示例17和18的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
6, ARRAY[10,7]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
22) 使用 多对一 来获取示例18和20的解决方案¶
路径 \(\{6, 12\}\rightarrow\{7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
ARRAY[6,12], 7
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
23) 使用 多对多 来获取示例17到20的解决方案¶
路径 \(\{6, 12\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
ARRAY[6, 12], ARRAY[10,7]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
24) 使用 组合 来获取示例17到19的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\cup\{12\}\rightarrow\{10\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)'
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
仅适用于带有 cost 列的 无向 图¶
仅有成本列的无向图¶
25) 从 \(6\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
6, 10,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 5 | 1 | 2
4 | 4 | 6 | 10 | 10 | -1 | 0 | 3
(4 rows)
26) 从 \(6\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
6, 7,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
(2 rows)
27)从 \(12\) 到 \(10\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
12, 10,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 12 | 10 | 12 | 11 | 1 | 0
2 | 2 | 12 | 10 | 11 | 5 | 1 | 1
3 | 3 | 12 | 10 | 10 | -1 | 0 | 2
(3 rows)
28) 从 \(12\) 到 \(7\) 的路径¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
12, 7,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 12 | 7 | 12 | 12 | 1 | 0
2 | 2 | 12 | 7 | 8 | 10 | 1 | 1
3 | 3 | 12 | 7 | 7 | -1 | 0 | 2
(3 rows)
29) 使用 一对多 来获取示例25和26的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
6, ARRAY[10,7],
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 5 | 1 | 2
6 | 4 | 6 | 10 | 10 | -1 | 0 | 3
(6 rows)
30) 使用 多对一 来获取示例26和28的解决方案¶
路径 \(\{6, 12\}\rightarrow\{7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
ARRAY[6,12], 7,
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 12 | 7 | 12 | 12 | 1 | 0
4 | 2 | 12 | 7 | 8 | 10 | 1 | 1
5 | 3 | 12 | 7 | 7 | -1 | 0 | 2
(5 rows)
31) 使用 多对多 来获取示例25到28的解决方案¶
路径 \(\{6, 12\}\rightarrow\{10, 7\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
ARRAY[6, 12], ARRAY[10,7],
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 5 | 1 | 2
6 | 4 | 6 | 10 | 10 | -1 | 0 | 3
7 | 1 | 12 | 7 | 12 | 12 | 1 | 0
8 | 2 | 12 | 7 | 8 | 10 | 1 | 1
9 | 3 | 12 | 7 | 7 | -1 | 0 | 2
10 | 1 | 12 | 10 | 12 | 11 | 1 | 0
11 | 2 | 12 | 10 | 11 | 5 | 1 | 1
12 | 3 | 12 | 10 | 10 | -1 | 0 | 2
(12 rows)
32) 使用 组合 来获取示例25到27的解决方案¶
路径 \(\{6\}\rightarrow\{10, 7\}\cup\{12\}\rightarrow\{10\}\)
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)',
false
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 5 | 1 | 2
6 | 4 | 6 | 10 | 10 | -1 | 0 | 3
7 | 1 | 12 | 10 | 12 | 11 | 1 | 0
8 | 2 | 12 | 10 | 11 | 5 | 1 | 1
9 | 3 | 12 | 10 | 10 | -1 | 0 | 2
(9 rows)
签名之间的等价性¶
下面的示例可以找到 \(\{6}\rightarrow\{10\}\) 的路径
33) 使用 一对一¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
34)使用 一对多¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, ARRAY[10]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
35) 使用 多对一¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6], 10
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
36) 使用 多对多¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6], ARRAY[10]
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
37) 使用 组合¶
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES(6, 10)) AS combinations (source, target)'
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
(6 rows)
另请参阅¶
索引和表格