From "Montreal" as the origin point, I’m trying to find the shortest path to go to another city. But I’m having diffulty when a city is looped.
For example, if to go LA there’s 2 ways, one that take 3 steps (MTL-NY-Detroit-LA) and the other takes 2 steps (MTL-Detroit-LA), I want that the shortest way to go to LA from Detroit to be shown.
I tried this code but I get the error on PostgresSQL:
recursive reference to query "shortestflight" must not appear within a subquery
LINE 16: FROM ShortestFlight
I was expecting that the shortest steps would be shown.
I would like to know an alternative so my code works.
WITH RECURSIVE ShortestFlight AS (
SELECT src, dst, cost, cost AS total_cost, 1 AS steps
FROM Flights
WHERE src="Montreal"
UNION
SELECT f.src, f.dst, f.cost, sf.total_cost + f.cost AS total_cost, sf.steps + 1
FROM Flights f
JOIN ShortestFlight sf ON f.src = sf.dst
WHERE NOT EXISTS (
SELECT 1
FROM ShortestFlight
WHERE sf2.dst = f.dst AND sf2.steps <= sf.steps + 1
)
)
SELECT *
FROM ShortestFlight
ORDER BY steps, total_cost;
You need to sign in to view this answers
Leave feedback about this