CODEWITHSUNDEEP
mysqlsql
DemCodeLines
DemCodeLines

Reputation: 1920

MySQL Shortest Path between two nodes

I have a MySQL table as defined below:

SELECT * FROM paths

source | destination
1 | 2
1 | 3
2 | 4
4 | 5
3 | 5

I am trying to find the shortest path between 1 and 5 and not sure what SQL query would get that result. This is what I have right now:

WITH RECURSIVE cte AS
(
  SELECT destination, CAST(destination AS CHAR(200)) AS path
  FROM paths WHERE source = 1
  UNION ALL
  SELECT c.destination, CONCAT(cte.path, ",", c.destination)
  FROM paths c JOIN cte ON cte.destination=c.source
)
SELECT * FROM cte ORDER BY path;

I am not sure how I would limit the query above to only find paths that end at 5. Example of what I am looking for:

All paths between 1 to 5:

In this case, the shortest path that I want the query to return is the second option.

Upvotes: 0

Views: 1238

Answers (1)

sticky bit
sticky bit

Reputation: 37472

You're not too far away. Just add the paths' lengths in the recursion. Then filter the final result for the destination node and use ORDER BY the paths' lengths and LIMIT to get only one shortest path (if there are more than one path with the minimum length one of them is chosen randomly).

WITH RECURSIVE
cte
AS
(
SELECT p.destination,
       concat(p.source, '->', p.destination) path,
       1 length
       FROM paths p
       WHERE p.source = 1
UNION ALL
SELECT p.destination,
       concat(c.path, '->', p.destination) path,
       c.length + 1 length
       FROM cte c
            INNER JOIN paths p
                       ON p.source = c.destination
       WHERE c.destination <> 5
)
SELECT c.path
       FROM cte c
       WHERE c.destination = 5
       ORDER BY c.length
       LIMIT 1;

db<>fiddle

One thing you might consider though is loop handling, if there can be loops in the graph. Unless node 5 is in such a loop you'd have an endless recursion.

Upvotes: 2

Related Questions