我正在 PostgreSQL 中进行递归 SQL 查询,以找到从蒙特利尔到达各个城市所需的最低成本。数据遵循有向无环图 (DAG) 结构,其中每个航班转机均以
Flights
表表示,其中包含 src
(源城市)、dst
(目的地城市)和 cost
(航班成本) .
例如:
Route 1: Montreal → Toronto → LA, total cost: $2000
Route 2: Montreal → Chicago → LA, total cost: $1800
在这种情况下,查询应仅返回到 LA 的最便宜路线,总费用为 1800 美元。
我编写的查询找到了最便宜的路径,但我正在寻找进一步优化它的指导。
具体来说,我想要:
关于改进此查询的性能或结构有什么建议吗?
感谢您的帮助!
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)
我会消除递归查询中的循环并在主查询中使用
DISTINCT ON
:
WITH RECURSIVE CheapestFlight AS
(
SELECT src, dst,
ARRAY[dst] AS path,
cost AS total_price
FROM Flights
WHERE src = 'Montreal'
UNION
SELECT cf.src, f.dst,
cf.path || f.dst AS path,
cf.total_price + f.cost AS total_price
FROM CheapestFlight cf
INNER JOIN Flights f ON f.src = cf.dst
WHERE NOT ARRAY[f.dst] <@ cf.path
)
SELECT DISTINCT ON (dst)
dst as destination,
total_price
FROM CheapestFlight cf
ORDER BY dst, total_price;
但这肯定不是最好的算法。