# Recursive query to find shortest path in graph

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

• If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection? Commented Feb 11, 2019 at 23:49

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