如何优化递归SQL查询以找到最便宜的路径

Question

我正在 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)

Answer 1

我会消除递归查询中的循环并在主查询中使用

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;

但这肯定不是最好的算法。