I’m working on a recursive SQL query in PostgreSQL to find the minimum cost required to reach various cities from Montreal. The data follows a directed acyclic graph (DAG) structure, where each flight connection is represented in a Flights table with columns src (source city), dst (destination city), and cost (flight cost).
For example:
Route 1: Montreal → Toronto → LA, total cost: $2000
Route 2: Montreal → Chicago → LA, total cost: $1800
In this case, the query should return only the cheapest route to LA with a total cost of $1800.
The query I’ve written finds the cheapest paths, but I’m looking for guidance on optimizing it further. Specifically, I want to:
Ensure the recursive query filters paths to maintain only the minimum total cost for each destination.
Avoid revisiting connections (or cities) that have already been included in a path.
Any suggestions on improving the performance or structure of this query?
Thanks for your help!
WITH RECURSIVE CheapestFlight AS (
SELECT src, dst, cost AS total_price
FROM Flights
WHERE src="Montreal"
UNION
SELECT cf.src, f.dst, cf.total_price + f.cost AS total_price
FROM CheapestFlight cf
INNER JOIN Flights f ON f.src = cf.dst
)
SELECT dst as destination, total_price
FROM CheapestFlight cf
WHERE total_price = (
SELECT MIN(total_price)
FROM CheapestFlight
WHERE dst = cf.dst
)
You need to sign in to view this answers