在联结表中查找两个ID之间的最短路径长度

Question

假设我有这样一个连接表：

id1 | id2
1   | 2
2   | 3
3   | 4
4   | 5

我希望能够查询两个ID之间的距离。例如(1,2)之间的距离为0，(1,5)之间的距离为3。

- Peter R

---

这两列是否必须按数字顺序排列？ - cdub

@cdub 是的，我会执行那个。 - Peter R

Answer 1

您可以使用递归CTE来遍历图形并查找所有间接路径及其成本。例如：

使用递归CTE可以遍历图形并查找所有间接路径及其成本。例如：

with recursive
c as (
  select id1 as f, id2 as t, '/' || id1 || '/' || id2 as path, 0 as cost 
  from t where id1 = 1 -- starting node
  union
  select c.f, t.id2, path || '/' || t.id2, c.cost + 1
  from c
  join t on t.id1 = c.t
),
m as (
  select min(cost) as min_cost from c where t = 5
)
select c.*
from c
join m on c.cost = m.min_cost
where c.t = 5

结果：

f t path       cost
- - ---------- ----
1 5 /1/2/3/4/5    3

<最初的回答> 我所用来测试这个功能的数据脚本如下所示：

create table t (
  id1 int,
  id2 int
);

insert into t values (1, 2), (2, 3), (3, 4), (4, 5);

奖励问题（同样的价格）：如果你想列出所有可能的路径及其成本，你可以运行以下查询：

（译者注：原文中的"Original Answer"暂未翻译，因为不确定上下文中是否有涵盖到该部分内容）

with recursive
c as (
  select id1 as f, id2 as t, '/' || id1 || '/' || id2 as path, 0 as cost from t
  union
  select c.f, t.id2, path || '/' || t.id2, c.cost + 1
  from c
  join t on t.id1 = c.t
)
select * from c

结果：

 f t path       cost 
 - - ---------- ---- 
 1 2 /1/2          0 
 2 3 /2/3          0 
 3 4 /3/4          0 
 4 5 /4/5          0 
 1 3 /1/2/3        1 
 2 4 /2/3/4        1 
 3 5 /3/4/5        1 
 1 4 /1/2/3/4      2 
 2 5 /2/3/4/5      2 
 1 5 /1/2/3/4/5    3 

- The Impaler

---

这是一个很好的解决方案，唯一的问题是当你在表中有这个递归时： id1 | id2 1 | 2 2 | 3 3 | 1 - Alexander S.