How to Optimise a Recursive SQL Query: to Find the Cheapest Path

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

Related Post