Recursive query to find shortest path in graph

Question

I have an assignment to find the shortest possible path between two people in a table. The table is Company(company_name, job, name), all of them not null, but none of them unique (primary key is the combination of all three values).

I'm supposed to use a recursive select query to find the shortest path between (for example) Bob Ross and Celine Dion. I know Bob is director of Painters, the manager of Painters is Carl, Carl is also an administrator in Sunny-D, and the director for Sunny-D is Celine Dion. So every name and company is a node, and the lines connecting them are the jobs. I'm not very good in SQL (we use PostgreSQL), and on top of that, I'm terrible at recursion, so if anyone could point me the right direction, I'd very much appreciate it.

What I have so far:

WITH RECURSIVE path(company_name, job, name, step) AS (
 SELECT c.company_name, c.job, c.name, 1
 FROM Company c
 WHERE person = 'Bob Ross'
 UNION ALL
 SELECT p.company_name, p.job, p.name, c.step+1
 FROM path p JOIN Company c ON p.person = c.person
 WHERE c.person = 'Celine Dion'
)
SELECT * FROM path;

I don't really know what to put in the recursive step where clause, or if I'm even joining them correctly

• ypercubeᵀᴹ: If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?

Answer 1

A recursive solution where the connections alternate between names and company_names.

The output shows all paths between the starting and ending node:

WITH RECURSIVE
conn AS
( SELECT
 name, company_name, job,
 (ROW_NUMBER() OVER (ORDER BY company_name, job))::text
 AS rn,
 CONCAT_WS(', ', name, company_name, job)::text
 AS node,
 1 AS lvl
 FROM
 company
 WHERE
 name = 'Bob Ross'
 UNION ALL
 SELECT
 b.name, b.company_name, b.job,
 CONCAT(a.rn, '-', (ROW_NUMBER()
 OVER (PARTITION BY a.rn
 ORDER BY b.name, b.company_name, b.job))::text),
 CONCAT(a.node, ' - ',
 CONCAT_WS(', ', b.name, b.company_name, b.job)),
 lvl + 1
 FROM
 conn AS a
 JOIN company AS b
 ON ( ( a.company_name = b.company_name
 AND a.name <> b.name AND a.lvl % 2 = 1
 )
 OR ( a.company_name <> b.company_name
 AND a.name = b.name AND a.lvl % 2 = 0
 )
 )
 AND a.name <> 'Celine Dion'
 AND b.name <> 'Bob Ross'
)
SELECT r.*
FROM conn AS f
 JOIN conn AS r 
 ON f.rn LIKE CONCAT(r.rn, '%')
WHERE f.name = 'Celine Dion' ;

Test at dbfiddle.uk