假设我有一个名为graph的表格:
_id |
relates |
|---|---|
1 |
{2, 3} |
2 |
{4} |
3 |
{5, 6} |
4 |
{3, 7} |
5 |
{} |
6 |
{} |
7 |
{} |
以下是图表形式: graph个
我的问题是编写一个递归查询来查找两个 node 之间的最短路径.在本例中，我的目标是找到 node 1和 node 3之间的最短路径.
下面的查询运行良好，并解决了问题.
with recursive pathFrom1to3(_id, relates, lvl, _path) as
(
select _id, relates, 1 as lvl, ARRAY[_id]
from graph
where _id = 1
union
select g._id, g.relates, p.lvl+1 as lvl, _path || g._id
from pathFrom1to3 p join graph g on g._id = any(p.relates)
where not g._id = any(p._path) -- handles cycles (not applicable for this example)
)
select * from pathFrom1To3
where _id = 3
limit 1
递归查询实际上从 node 1开始查找all条可能的路径，直到它找不到更多的路径，因此在递归结束后，我们只剩下这个表:
_id |
relates |
lvl |
_path |
|---|---|---|---|
1 |
{2, 3} |
1 |
{1} |
2 |
{4} |
2 |
{1, 2} |
3 |
{5, 6} |
2 |
{1, 3} |
4 |
{3, 7} |
3 |
{1, 2, 4} |
5 |
{} |
3 |
{1, 3, 5} |
6 |
{} |
3 |
{1, 3, 6} |
3 |
{5, 6} |
4 |
{1, 2, 4, 3} |
7 |
{} |
4 |
{1, 2, 4, 7} |
5 |
{} |
5 |
{1, 2, 4, 3, 5} |
6 |
{} |
5 |
{1, 2, 4, 3, 6} |
在我们筛选出_id = 3个之后，我们得到:
_id |
relates |
lvl |
_path |
|---|---|---|---|
3 |
{5, 6} |
2 |
{1, 3} |
3 |
{5, 6} |
4 |
{1, 2, 4, 3} |
通常情况下，最短的路径是我们最先击中的路径(因为边没有权重).按照我们查询的逻辑，这将等同于最早返回的记录，因此我们可以对此使用Limit:Limit 1
_id |
relates |
lvl |
_path |
|---|---|---|---|
3 |
{5, 6} |
2 |
{1, 2, 4} |
并且存在从 node 1到 node 3的最短路径.
我的问题是，该查询计算从 node 1开始的all条路径，如果目标 node 接近搜索开始，则效率非常低.我的目标是让查询在命中目标 node 后立即(完全)停止搜索，因为我们知道不会有其他最短路径.
I need a way to terminate the recursion completely when node 3 is reached.个
如果我try 为 node 本身添加终止符，如下面的查询，则相同级别的其他 node 的递归将继续，因为终止条件仍然满足:
with recursive pathFrom1to3(_id, relates, lvl, _path) as
(
select _id, relates, 1 as lvl, ARRAY[_id]
from graph
where _id = 1
union
select g._id, g.relates, p.lvl+1 as lvl, _path || g._id
from pathFrom1to3 p join graph g on g._id = any(p.relates)
where not g._id = any(p._path) -- handles cycles (not applicable for this example)
**and not p._id = 3**
)
select * from pathFrom1To3
产生:
| _id | relates | lvl | _path |
|---|---|---|---|
1 |
{2, 3} |
1 |
{1} |
2 |
{4} |
2 |
{1, 2} |
3 |
{5, 6} |
2 |
{1, 3} |
4 |
{3, 7} |
3 |
{1, 2, 4} |
3 |
{5, 6} |
4 |
{1, 2, 4, 3} |
7 |
{} |
4 |
{1, 2, 4, 7} |
5 |
{} |
5 |
{1, 2, 4, 3, 5} |
6 |
{} |
5 |
{1, 2, 4, 3, 6} |
注意，当第一次到达 node 3时，递归停止；不会进一步搜索 node 5和6，因为 node 3被击中.但是对于 node 4(从 node 2)递归继续，因为p.id不是3，而是2.
当递归到达 node 3for the entire level时，我们需要一种方法来终止递归.
我的 idea 是创建一个reached列，当_id不是3时为0，当_id为3时为1. 然后我们可以使用SUM来判断整个级别达到的值的总和，如果它不是0，那么我们将终止，但我正在努力将其作为一个查询来编写.
以下是我写这篇文章的try :
with recursive pathFrom1to3(_id, relates, lvl, _path, reached, lvlReached) as
(
select _id, relates, 1 as lvl, ARRAY[_id], 0 as reached, 0 as lvlReached
from graph
where _id = 1
union
select _id, relates, lvl, _path, reached, lvlReached from
(
select g._id, g.relates, p.lvl+1 as lvl, _path || g._id,
case when 3 = any(g.relates) then 1 else 0 end as reached
from pathFrom1to3 p join graph g on g._id = any(p.relates)
where not g._id = any(p._path) -- handles cycles
) mainRecursion
join
(
select lvl, sum(reached) as lvlReached
from pathFrom1To3
group by lvl
) lvlReached
on mainRecursion.lvl = lvlReach.lvl
where lvlReached = 0
)
select * from pathFrom1To3
这给了我一个错误:
recursive reference to query "pathFrom1to3" must not appear more than once.