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

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