Postgresql – 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,, 1
        FROM Company c
        WHERE person = 'Bob Ross'

        UNION ALL

    SELECT p.company_name, p.job,, c.step+1
    FROM path p JOIN Company c ON p.person = c.person
    WHERE c.person = 'Celine Dion'

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

Best Answer

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

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

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

Test at