递归查询shortestflight子查询引用报错，求最短航班路径SQL方案

你要实现的是从Montreal出发，找到到各城市的最少步数航班路径，同时解决循环问题和原代码的语法错误。原代码报错的原因是：PostgreSQL不允许递归CTE的递归分支在子查询中引用自身，所以WHERE NOT EXISTS里的ShortestFlight引用违反了语法规则。

可行方案：跟踪路径+筛选最优结果 #

我们可以通过记录已访问城市避免循环，再用窗口函数筛选每个城市的最少步数路径（步数相同则选成本最低的），具体实现如下：

完整SQL代码 #

CREATE TABLE flights(id,src,dst,cost) AS VALUES
 (0,'Montreal','NY',      742.94)
,(1,'Montreal','Detroit', 362.47)
,(2,'NY',      'Detroit', 936.60)
,(3,'Detroit', 'LA',      64.32 )
,(4,'NY',      'Montreal',94.26 )
,(5,'Detroit', 'NY',      213.86)
,(6,'LA',      'Detroit', 490.88);

WITH RECURSIVE flight_paths AS (
    -- 初始直飞航班
    SELECT 
        src,
        dst,
        cost AS total_cost,
        1 AS steps,
        ARRAY[src, dst] AS path  -- 用数组记录完整路径
    FROM flights
    WHERE src = 'Montreal'

    UNION ALL

    -- 递归扩展路径，避免循环
    SELECT 
        fp.src,
        f.dst,
        fp.total_cost + f.cost AS total_cost,
        fp.steps + 1 AS steps,
        fp.path || f.dst AS path
    FROM flight_paths fp
    JOIN flights f ON fp.dst = f.src
    WHERE NOT (f.dst = ANY(fp.path))  -- 不回到已访问过的城市
),
-- 筛选每个目标城市的最优路径
shortest_paths AS (
    SELECT 
        *,
        ROW_NUMBER() OVER (
            PARTITION BY dst 
            ORDER BY steps ASC, total_cost ASC
        ) AS rn
    FROM flight_paths
)
SELECT src, dst, total_cost, steps, path
FROM shortest_paths
WHERE rn = 1
ORDER BY steps, total_cost;

逻辑说明 #

• 初始分支：获取从Montreal出发的所有直飞航班，初始化路径数组、步数和总成本。
• 递归分支：通过连接航班表扩展路径，用NOT (f.dst = ANY(fp.path))确保不会重复访问城市，彻底避免循环。
• 筛选最优路径：用ROW_NUMBER()窗口函数按目标城市分组，先按步数升序排序（优先最少步数），步数相同则按总成本升序排序，最后筛选出每组的第一条记录，就是该城市的最优路径。

最终结果 #

执行后会得到符合需求的结果：

• Montreal → NY（1步，总成本742.94）
• Montreal → Detroit（1步，总成本362.47）
• Montreal → Detroit → LA（2步，总成本426.79）

这样既解决了原有的语法错误，又精准实现了“优先最少步数”的需求，同时避免了城市循环问题。

内容的提问来源于stack exchange，提问作者NoobAtProgramming