CODEWITHSUNDEEP
sqlpostgresql
Peter R
Peter R

Reputation: 3516

Finding shortest path length between two IDs in a join table

Let's say I have a join table like this

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

I want to be able to query the distance between two IDs. So for (1,2) would it would be 0. for (1,5) it would be 3.

Upvotes: 3

Views: 239

Answers (1)

The Impaler
The Impaler

Reputation: 48810

You can use a recursive CTE to walk the graph and find all indirect paths and their costs. For example:

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

Result:

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

For the record, here's data script I used to test it:

create table t (
  id1 int,
  id2 int
);

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

Bonus query (for the same price): If you wanted to list all possible paths and their costs you could run the query:

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

Result:

 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

Upvotes: 2

Related Questions