sql - 在连接表中查找两个 ID 之间的最短路径长度

Question

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

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

我希望能够查询两个 ID 之间的距离。 所以对于 (1,2) 它将是 0。对于 (1,5) 它将是 3。

Answer 1

您可以使用递归 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);

奖励查询(价格相同):如果您想列出所有可能的路径及其成本，您可以运行查询:

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