pgr_KSP¶
pgr_KSP — Yen 使用 Dijkstra 计算 K 最短路径的算法。
Boost 图内部¶
可用性
版本3.6.0
结果列标准化为
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)pgr_ksp(一对一)增加
start_vid和end_vid结果列。
新的重载函数：
pgr_ksp(一对多)pgr_ksp(多对一)pgr_ksp(多对多)pgr_ksp(组合)
版本2.1.0
签名变更
不再支持旧签名
版本2.0.0
官方 函数
描述¶
基于Yen算法的K最短路径路由算法。 “K”是所需的最短路径的数量。
签名¶
总结
pgr_KSP(Edges SQL, start vid, end vid, K, [options])
pgr_KSP(Edges SQL, start vid, end vids, K, [options])
pgr_KSP(Edges SQL, start vids, end vid, K, [options])
pgr_KSP(Edges SQL, start vids, end vids, K, [options])
pgr_KSP(Edges SQL, Combinations SQL, K, [options])
options:
[directed, heap_paths]返回集合
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
一对一¶
pgr_KSP(Edges SQL, start vid, end vid, K, [options])
options:
[directed, heap_paths]返回集合
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在有向图上获取从 \(6\) 到 \(17\) 的 2 条路径。
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 17, 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 17 | 6 | 4 | 1 | 0
2 | 1 | 2 | 6 | 17 | 7 | 10 | 1 | 1
3 | 1 | 3 | 6 | 17 | 8 | 12 | 1 | 2
4 | 1 | 4 | 6 | 17 | 12 | 13 | 1 | 3
5 | 1 | 5 | 6 | 17 | 17 | -1 | 0 | 4
6 | 2 | 1 | 6 | 17 | 6 | 4 | 1 | 0
7 | 2 | 2 | 6 | 17 | 7 | 8 | 1 | 1
8 | 2 | 3 | 6 | 17 | 11 | 9 | 1 | 2
9 | 2 | 4 | 6 | 17 | 16 | 15 | 1 | 3
10 | 2 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(10 rows)
一对多¶
pgr_KSP(Edges SQL, start vid, end vids, K, [options])
options:
[directed, heap_paths]返回集合
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
获取有向图上从顶点 \(6\) 到顶点 \(\{10, 17\}\) 的 2 条路径。
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
6, ARRAY[10, 17], 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 1 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 1 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 1 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 1 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 1 | 6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 2 | 1 | 6 | 10 | 6 | 4 | 1 | 0
8 | 2 | 2 | 6 | 10 | 7 | 10 | 1 | 1
9 | 2 | 3 | 6 | 10 | 8 | 12 | 1 | 2
10 | 2 | 4 | 6 | 10 | 12 | 13 | 1 | 3
11 | 2 | 5 | 6 | 10 | 17 | 15 | 1 | 4
12 | 2 | 6 | 6 | 10 | 16 | 16 | 1 | 5
13 | 2 | 7 | 6 | 10 | 15 | 3 | 1 | 6
14 | 2 | 8 | 6 | 10 | 10 | -1 | 0 | 7
15 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
16 | 3 | 2 | 6 | 17 | 7 | 10 | 1 | 1
17 | 3 | 3 | 6 | 17 | 8 | 12 | 1 | 2
18 | 3 | 4 | 6 | 17 | 12 | 13 | 1 | 3
19 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
20 | 4 | 1 | 6 | 17 | 6 | 4 | 1 | 0
21 | 4 | 2 | 6 | 17 | 7 | 8 | 1 | 1
22 | 4 | 3 | 6 | 17 | 11 | 9 | 1 | 2
23 | 4 | 4 | 6 | 17 | 16 | 15 | 1 | 3
24 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(24 rows)
多对一¶
pgr_KSP(Edges SQL, start vids, end vid, K, [options])
options:
[directed, heap_paths]返回集合
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在有向图中得到从顶点 \(\{6, 1\}\) 到顶点 \(17\) 的2条路经。
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17, 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 17 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 17 | 7 | 10 | 1 | 2
4 | 1 | 4 | 1 | 17 | 8 | 12 | 1 | 3
5 | 1 | 5 | 1 | 17 | 12 | 13 | 1 | 4
6 | 1 | 6 | 1 | 17 | 17 | -1 | 0 | 5
7 | 2 | 1 | 1 | 17 | 1 | 6 | 1 | 0
8 | 2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
9 | 2 | 3 | 1 | 17 | 7 | 8 | 1 | 2
10 | 2 | 4 | 1 | 17 | 11 | 9 | 1 | 3
11 | 2 | 5 | 1 | 17 | 16 | 15 | 1 | 4
12 | 2 | 6 | 1 | 17 | 17 | -1 | 0 | 5
13 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
14 | 3 | 2 | 6 | 17 | 7 | 10 | 1 | 1
15 | 3 | 3 | 6 | 17 | 8 | 12 | 1 | 2
16 | 3 | 4 | 6 | 17 | 12 | 13 | 1 | 3
17 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
18 | 4 | 1 | 6 | 17 | 6 | 4 | 1 | 0
19 | 4 | 2 | 6 | 17 | 7 | 8 | 1 | 1
20 | 4 | 3 | 6 | 17 | 11 | 9 | 1 | 2
21 | 4 | 4 | 6 | 17 | 16 | 15 | 1 | 3
22 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(22 rows)
多对多¶
pgr_KSP(Edges SQL, start vids, end vids, K, [options])
options:
[directed, heap_paths]返回集合
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)OR EMPTY SET
- 示例:
在有向图中得到从顶点 \(\{6, 1\}\) 到顶点 \(\{10, 17\}\) 的2条路经。
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17], 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 10 | 7 | 8 | 1 | 2
4 | 1 | 4 | 1 | 10 | 11 | 9 | 1 | 3
5 | 1 | 5 | 1 | 10 | 16 | 16 | 1 | 4
6 | 1 | 6 | 1 | 10 | 15 | 3 | 1 | 5
7 | 1 | 7 | 1 | 10 | 10 | -1 | 0 | 6
8 | 2 | 1 | 1 | 10 | 1 | 6 | 1 | 0
9 | 2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
10 | 2 | 3 | 1 | 10 | 7 | 10 | 1 | 2
11 | 2 | 4 | 1 | 10 | 8 | 12 | 1 | 3
12 | 2 | 5 | 1 | 10 | 12 | 13 | 1 | 4
13 | 2 | 6 | 1 | 10 | 17 | 15 | 1 | 5
14 | 2 | 7 | 1 | 10 | 16 | 16 | 1 | 6
15 | 2 | 8 | 1 | 10 | 15 | 3 | 1 | 7
16 | 2 | 9 | 1 | 10 | 10 | -1 | 0 | 8
17 | 3 | 1 | 1 | 17 | 1 | 6 | 1 | 0
18 | 3 | 2 | 1 | 17 | 3 | 7 | 1 | 1
19 | 3 | 3 | 1 | 17 | 7 | 10 | 1 | 2
20 | 3 | 4 | 1 | 17 | 8 | 12 | 1 | 3
21 | 3 | 5 | 1 | 17 | 12 | 13 | 1 | 4
22 | 3 | 6 | 1 | 17 | 17 | -1 | 0 | 5
23 | 4 | 1 | 1 | 17 | 1 | 6 | 1 | 0
24 | 4 | 2 | 1 | 17 | 3 | 7 | 1 | 1
25 | 4 | 3 | 1 | 17 | 7 | 8 | 1 | 2
26 | 4 | 4 | 1 | 17 | 11 | 9 | 1 | 3
27 | 4 | 5 | 1 | 17 | 16 | 15 | 1 | 4
28 | 4 | 6 | 1 | 17 | 17 | -1 | 0 | 5
29 | 5 | 1 | 6 | 10 | 6 | 4 | 1 | 0
30 | 5 | 2 | 6 | 10 | 7 | 8 | 1 | 1
31 | 5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
32 | 5 | 4 | 6 | 10 | 16 | 16 | 1 | 3
33 | 5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
34 | 5 | 6 | 6 | 10 | 10 | -1 | 0 | 5
35 | 6 | 1 | 6 | 10 | 6 | 4 | 1 | 0
36 | 6 | 2 | 6 | 10 | 7 | 10 | 1 | 1
37 | 6 | 3 | 6 | 10 | 8 | 12 | 1 | 2
38 | 6 | 4 | 6 | 10 | 12 | 13 | 1 | 3
39 | 6 | 5 | 6 | 10 | 17 | 15 | 1 | 4
40 | 6 | 6 | 6 | 10 | 16 | 16 | 1 | 5
41 | 6 | 7 | 6 | 10 | 15 | 3 | 1 | 6
42 | 6 | 8 | 6 | 10 | 10 | -1 | 0 | 7
43 | 7 | 1 | 6 | 17 | 6 | 4 | 1 | 0
44 | 7 | 2 | 6 | 17 | 7 | 10 | 1 | 1
45 | 7 | 3 | 6 | 17 | 8 | 12 | 1 | 2
46 | 7 | 4 | 6 | 17 | 12 | 13 | 1 | 3
47 | 7 | 5 | 6 | 17 | 17 | -1 | 0 | 4
48 | 8 | 1 | 6 | 17 | 6 | 4 | 1 | 0
49 | 8 | 2 | 6 | 17 | 7 | 8 | 1 | 1
50 | 8 | 3 | 6 | 17 | 11 | 9 | 1 | 2
51 | 8 | 4 | 6 | 17 | 16 | 15 | 1 | 3
52 | 8 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(52 rows)
组合¶
pgr_KSP(Edges SQL, Combinations SQL, K, [options])
options:
[directed, heap_paths]返回集合
(seq, path_id, 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_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations', 2);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 2 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 2 | 5 | 10 | 6 | 4 | 1 | 1
5 | 2 | 3 | 5 | 10 | 7 | 8 | 1 | 2
6 | 2 | 4 | 5 | 10 | 11 | 9 | 1 | 3
7 | 2 | 5 | 5 | 10 | 16 | 16 | 1 | 4
8 | 2 | 6 | 5 | 10 | 15 | 3 | 1 | 5
9 | 2 | 7 | 5 | 10 | 10 | -1 | 0 | 6
10 | 3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
11 | 3 | 2 | 5 | 10 | 6 | 4 | 1 | 1
12 | 3 | 3 | 5 | 10 | 7 | 10 | 1 | 2
13 | 3 | 4 | 5 | 10 | 8 | 12 | 1 | 3
14 | 3 | 5 | 5 | 10 | 12 | 13 | 1 | 4
15 | 3 | 6 | 5 | 10 | 17 | 15 | 1 | 5
16 | 3 | 7 | 5 | 10 | 16 | 16 | 1 | 6
17 | 3 | 8 | 5 | 10 | 15 | 3 | 1 | 7
18 | 3 | 9 | 5 | 10 | 10 | -1 | 0 | 8
19 | 4 | 1 | 6 | 5 | 6 | 1 | 1 | 0
20 | 4 | 2 | 6 | 5 | 5 | -1 | 0 | 1
21 | 5 | 1 | 6 | 15 | 6 | 4 | 1 | 0
22 | 5 | 2 | 6 | 15 | 7 | 8 | 1 | 1
23 | 5 | 3 | 6 | 15 | 11 | 9 | 1 | 2
24 | 5 | 4 | 6 | 15 | 16 | 16 | 1 | 3
25 | 5 | 5 | 6 | 15 | 15 | -1 | 0 | 4
26 | 6 | 1 | 6 | 15 | 6 | 4 | 1 | 0
27 | 6 | 2 | 6 | 15 | 7 | 10 | 1 | 1
28 | 6 | 3 | 6 | 15 | 8 | 12 | 1 | 2
29 | 6 | 4 | 6 | 15 | 12 | 13 | 1 | 3
30 | 6 | 5 | 6 | 15 | 17 | 15 | 1 | 4
31 | 6 | 6 | 6 | 15 | 16 | 16 | 1 | 5
32 | 6 | 7 | 6 | 15 | 15 | -1 | 0 | 6
(32 rows)
参数¶
列 |
类型 |
描述 |
|---|---|---|
|
如所述的 SQL 查询。 |
|
start vid |
ANY-INTEGER |
出发顶点的标识符。 |
end vid |
ANY-INTEGER |
目标顶点的标识符。 |
K |
ANY-INTEGER |
所需路径的数量。 |
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT
可选参数¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
|
|
|
KSP 可选参数¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
|
|
|
内部查询¶
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_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
列 |
类型 |
描述 |
|---|---|---|
|
|
从 1 开始的顺序值。 |
|
|
路径标识符。
|
|
|
路径中的相对位置。 路径开头的值为 1。 |
|
|
从 |
|
|
用于从路径序列中的 |
|
|
从使用
|
|
|
从 start vid 到 |
其他示例¶
- 示例:
在无向图中获取从 \(6\) 到 \(17\) 的2条路径
还获取堆中的路径。
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 17, 2,
directed => false, heap_paths => true
);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 6 | 17 | 6 | 4 | 1 | 0
2 | 1 | 2 | 6 | 17 | 7 | 10 | 1 | 1
3 | 1 | 3 | 6 | 17 | 8 | 12 | 1 | 2
4 | 1 | 4 | 6 | 17 | 12 | 13 | 1 | 3
5 | 1 | 5 | 6 | 17 | 17 | -1 | 0 | 4
6 | 2 | 1 | 6 | 17 | 6 | 4 | 1 | 0
7 | 2 | 2 | 6 | 17 | 7 | 8 | 1 | 1
8 | 2 | 3 | 6 | 17 | 11 | 11 | 1 | 2
9 | 2 | 4 | 6 | 17 | 12 | 13 | 1 | 3
10 | 2 | 5 | 6 | 17 | 17 | -1 | 0 | 4
11 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
12 | 3 | 2 | 6 | 17 | 7 | 8 | 1 | 1
13 | 3 | 3 | 6 | 17 | 11 | 9 | 1 | 2
14 | 3 | 4 | 6 | 17 | 16 | 15 | 1 | 3
15 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
16 | 4 | 1 | 6 | 17 | 6 | 2 | 1 | 0
17 | 4 | 2 | 6 | 17 | 10 | 5 | 1 | 1
18 | 4 | 3 | 6 | 17 | 11 | 9 | 1 | 2
19 | 4 | 4 | 6 | 17 | 16 | 15 | 1 | 3
20 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(20 rows)
- 示例:
使用无向图上的组合表获取 2 条路径
还获取堆中的路径。
SELECT * FROM pgr_KSP(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations', 2, directed => false, heap_paths => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 1 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 2 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 2 | 5 | 10 | 6 | 2 | 1 | 1
5 | 2 | 3 | 5 | 10 | 10 | -1 | 0 | 2
6 | 3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
7 | 3 | 2 | 5 | 10 | 6 | 4 | 1 | 1
8 | 3 | 3 | 5 | 10 | 7 | 8 | 1 | 2
9 | 3 | 4 | 5 | 10 | 11 | 5 | 1 | 3
10 | 3 | 5 | 5 | 10 | 10 | -1 | 0 | 4
11 | 4 | 1 | 6 | 5 | 6 | 1 | 1 | 0
12 | 4 | 2 | 6 | 5 | 5 | -1 | 0 | 1
13 | 5 | 1 | 6 | 15 | 6 | 2 | 1 | 0
14 | 5 | 2 | 6 | 15 | 10 | 3 | 1 | 1
15 | 5 | 3 | 6 | 15 | 15 | -1 | 0 | 2
16 | 6 | 1 | 6 | 15 | 6 | 4 | 1 | 0
17 | 6 | 2 | 6 | 15 | 7 | 8 | 1 | 1
18 | 6 | 3 | 6 | 15 | 11 | 9 | 1 | 2
19 | 6 | 4 | 6 | 15 | 16 | 16 | 1 | 3
20 | 6 | 5 | 6 | 15 | 15 | -1 | 0 | 4
21 | 7 | 1 | 6 | 15 | 6 | 2 | 1 | 0
22 | 7 | 2 | 6 | 15 | 10 | 5 | 1 | 1
23 | 7 | 3 | 6 | 15 | 11 | 9 | 1 | 2
24 | 7 | 4 | 6 | 15 | 16 | 16 | 1 | 3
25 | 7 | 5 | 6 | 15 | 15 | -1 | 0 | 4
(25 rows)
- 示例:
在无向图中获取从顶点 \(\{6, 1\}\) 到顶点 \(17\) 的2条路径。
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17, 2, directed => false);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 17 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 17 | 7 | 10 | 1 | 2
4 | 1 | 4 | 1 | 17 | 8 | 12 | 1 | 3
5 | 1 | 5 | 1 | 17 | 12 | 13 | 1 | 4
6 | 1 | 6 | 1 | 17 | 17 | -1 | 0 | 5
7 | 2 | 1 | 1 | 17 | 1 | 6 | 1 | 0
8 | 2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
9 | 2 | 3 | 1 | 17 | 7 | 8 | 1 | 2
10 | 2 | 4 | 1 | 17 | 11 | 9 | 1 | 3
11 | 2 | 5 | 1 | 17 | 16 | 15 | 1 | 4
12 | 2 | 6 | 1 | 17 | 17 | -1 | 0 | 5
13 | 3 | 1 | 6 | 17 | 6 | 4 | 1 | 0
14 | 3 | 2 | 6 | 17 | 7 | 10 | 1 | 1
15 | 3 | 3 | 6 | 17 | 8 | 12 | 1 | 2
16 | 3 | 4 | 6 | 17 | 12 | 13 | 1 | 3
17 | 3 | 5 | 6 | 17 | 17 | -1 | 0 | 4
18 | 4 | 1 | 6 | 17 | 6 | 4 | 1 | 0
19 | 4 | 2 | 6 | 17 | 7 | 8 | 1 | 1
20 | 4 | 3 | 6 | 17 | 11 | 11 | 1 | 2
21 | 4 | 4 | 6 | 17 | 12 | 13 | 1 | 3
22 | 4 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(22 rows)
- 示例:
在有向图中得到从顶点 \(\{6, 1\}\) 到顶点 \(\{10, 17\}\) 的2条路经。
还获取堆中的路径。
SELECT * FROM pgr_KSP(
'select id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17], 2, heap_paths => true);
seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 1 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 1 | 3 | 1 | 10 | 7 | 8 | 1 | 2
4 | 1 | 4 | 1 | 10 | 11 | 9 | 1 | 3
5 | 1 | 5 | 1 | 10 | 16 | 16 | 1 | 4
6 | 1 | 6 | 1 | 10 | 15 | 3 | 1 | 5
7 | 1 | 7 | 1 | 10 | 10 | -1 | 0 | 6
8 | 2 | 1 | 1 | 10 | 1 | 6 | 1 | 0
9 | 2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
10 | 2 | 3 | 1 | 10 | 7 | 10 | 1 | 2
11 | 2 | 4 | 1 | 10 | 8 | 12 | 1 | 3
12 | 2 | 5 | 1 | 10 | 12 | 13 | 1 | 4
13 | 2 | 6 | 1 | 10 | 17 | 15 | 1 | 5
14 | 2 | 7 | 1 | 10 | 16 | 16 | 1 | 6
15 | 2 | 8 | 1 | 10 | 15 | 3 | 1 | 7
16 | 2 | 9 | 1 | 10 | 10 | -1 | 0 | 8
17 | 3 | 1 | 1 | 10 | 1 | 6 | 1 | 0
18 | 3 | 2 | 1 | 10 | 3 | 7 | 1 | 1
19 | 3 | 3 | 1 | 10 | 7 | 8 | 1 | 2
20 | 3 | 4 | 1 | 10 | 11 | 11 | 1 | 3
21 | 3 | 5 | 1 | 10 | 12 | 13 | 1 | 4
22 | 3 | 6 | 1 | 10 | 17 | 15 | 1 | 5
23 | 3 | 7 | 1 | 10 | 16 | 16 | 1 | 6
24 | 3 | 8 | 1 | 10 | 15 | 3 | 1 | 7
25 | 3 | 9 | 1 | 10 | 10 | -1 | 0 | 8
26 | 4 | 1 | 1 | 17 | 1 | 6 | 1 | 0
27 | 4 | 2 | 1 | 17 | 3 | 7 | 1 | 1
28 | 4 | 3 | 1 | 17 | 7 | 10 | 1 | 2
29 | 4 | 4 | 1 | 17 | 8 | 12 | 1 | 3
30 | 4 | 5 | 1 | 17 | 12 | 13 | 1 | 4
31 | 4 | 6 | 1 | 17 | 17 | -1 | 0 | 5
32 | 5 | 1 | 1 | 17 | 1 | 6 | 1 | 0
33 | 5 | 2 | 1 | 17 | 3 | 7 | 1 | 1
34 | 5 | 3 | 1 | 17 | 7 | 8 | 1 | 2
35 | 5 | 4 | 1 | 17 | 11 | 11 | 1 | 3
36 | 5 | 5 | 1 | 17 | 12 | 13 | 1 | 4
37 | 5 | 6 | 1 | 17 | 17 | -1 | 0 | 5
38 | 6 | 1 | 1 | 17 | 1 | 6 | 1 | 0
39 | 6 | 2 | 1 | 17 | 3 | 7 | 1 | 1
40 | 6 | 3 | 1 | 17 | 7 | 8 | 1 | 2
41 | 6 | 4 | 1 | 17 | 11 | 9 | 1 | 3
42 | 6 | 5 | 1 | 17 | 16 | 15 | 1 | 4
43 | 6 | 6 | 1 | 17 | 17 | -1 | 0 | 5
44 | 7 | 1 | 6 | 10 | 6 | 4 | 1 | 0
45 | 7 | 2 | 6 | 10 | 7 | 8 | 1 | 1
46 | 7 | 3 | 6 | 10 | 11 | 9 | 1 | 2
47 | 7 | 4 | 6 | 10 | 16 | 16 | 1 | 3
48 | 7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
49 | 7 | 6 | 6 | 10 | 10 | -1 | 0 | 5
50 | 8 | 1 | 6 | 10 | 6 | 4 | 1 | 0
51 | 8 | 2 | 6 | 10 | 7 | 10 | 1 | 1
52 | 8 | 3 | 6 | 10 | 8 | 12 | 1 | 2
53 | 8 | 4 | 6 | 10 | 12 | 13 | 1 | 3
54 | 8 | 5 | 6 | 10 | 17 | 15 | 1 | 4
55 | 8 | 6 | 6 | 10 | 16 | 16 | 1 | 5
56 | 8 | 7 | 6 | 10 | 15 | 3 | 1 | 6
57 | 8 | 8 | 6 | 10 | 10 | -1 | 0 | 7
58 | 9 | 1 | 6 | 10 | 6 | 4 | 1 | 0
59 | 9 | 2 | 6 | 10 | 7 | 8 | 1 | 1
60 | 9 | 3 | 6 | 10 | 11 | 11 | 1 | 2
61 | 9 | 4 | 6 | 10 | 12 | 13 | 1 | 3
62 | 9 | 5 | 6 | 10 | 17 | 15 | 1 | 4
63 | 9 | 6 | 6 | 10 | 16 | 16 | 1 | 5
64 | 9 | 7 | 6 | 10 | 15 | 3 | 1 | 6
65 | 9 | 8 | 6 | 10 | 10 | -1 | 0 | 7
66 | 10 | 1 | 6 | 17 | 6 | 4 | 1 | 0
67 | 10 | 2 | 6 | 17 | 7 | 10 | 1 | 1
68 | 10 | 3 | 6 | 17 | 8 | 12 | 1 | 2
69 | 10 | 4 | 6 | 17 | 12 | 13 | 1 | 3
70 | 10 | 5 | 6 | 17 | 17 | -1 | 0 | 4
71 | 11 | 1 | 6 | 17 | 6 | 4 | 1 | 0
72 | 11 | 2 | 6 | 17 | 7 | 8 | 1 | 1
73 | 11 | 3 | 6 | 17 | 11 | 11 | 1 | 2
74 | 11 | 4 | 6 | 17 | 12 | 13 | 1 | 3
75 | 11 | 5 | 6 | 17 | 17 | -1 | 0 | 4
76 | 12 | 1 | 6 | 17 | 6 | 4 | 1 | 0
77 | 12 | 2 | 6 | 17 | 7 | 8 | 1 | 1
78 | 12 | 3 | 6 | 17 | 11 | 9 | 1 | 2
79 | 12 | 4 | 6 | 17 | 16 | 15 | 1 | 3
80 | 12 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(80 rows)
另请参阅¶
索引和表格