如何在一张桌子内找到转机

Question

我正在练习SQL，我有一个名为flights的表，其中包含此次旅行的航班id、origin、destination和cost。我希望能够找到所有最便宜的航班，这些航班可以在两个或更少的站点内完成，同时还显示每个航班有多少个站点以及航班的总成本。此外，如果两次旅行的费用相同，那么我想要停站最少的一次。

这是db fiddle上的表格：https://www.db-fiddle.com/f/mvvE24KAxnayR9fRmHChMw/1

这就是我到目前为止所做的，它还没有完成，因为我错过了停靠站和一些航班的数量。我不确定如何计算航班之间的停靠次数，也不确定如何获得所有正在转机的航班。

我觉得这可以在没有递归CTE的情况下完成，但我不确定。我也觉得我的问题很混乱。任何帮助都是有用的！

谢谢！

查询：

WITH RECURSIVE connecting_flights AS (
SELECT origin, destination, cost 
FROM flights
UNION ALL
SELECT f.origin, f.destination, cf.cost
FROM flights f
INNER JOIN connecting_flights cf ON cf.origin = f.destination
), flight_data as (
SELECT 
DISTINCT flights.origin as original_flight
, flights.destination as original_destination
, flights.cost as flights_cost
, cf.origin as cf_origin
, cf.destination as cf_destination
,cf.cost as cf_cost
, flights.cost + cf.cost as total_cost
FROM flights
LEFT JOIN connecting_flights cf ON cf.origin = flights.destination
LEFT JOIN flights b ON b.origin = cf.origin
) 
SELECT
original_flight
, CASE 
WHEN cf_destination IS NULL THEN original_destination
ELSE cf_destination
END as destination
, CASE
WHEN cf_destination IS NULL THEN flights_cost
ELSE total_cost
END as total
FROM flight_data
ORDER BY original_flight

Answer 1

这里有一种使用递归cte选项的方法。在这里，您可以选择根和目的地，并找出花费最少的站点和最少的

with recursive cte
as(select origin,destination,cast(destination as varchar(1000)) as str_path,origin as root,cost,0 as lvl 
from flights
union all
select ua.origin,ua.destination,cast(concat(str_path,'-',ua.destination) as varchar(1000)),c.root,c.cost+ua.cost,c.lvl+1
from cte c
join flights ua
on c.destination=ua.origin
and c.str_path not like concat('%',ua.destination,'%')  
)
select * from cte  order by 4,2,cost asc 
+--------+-------------+-------------+------+------+-----+
| origin | destination |  str_path   | root | cost | lvl |
+--------+-------------+-------------+------+------+-----+
| DFW    | JFK         | JFK         | DFW  |  200 |   0 |
| JFK    | LHR         | JFK-LHR     | DFW  | 1200 |   1 |
| DFW    | MCO         | MCO         | DFW  |  100 |   0 |
| JFK    | LHR         | LHR         | JFK  | 1000 |   0 |
| SFO    | DFW         | DFW         | SFO  |  200 |   0 |
| DFW    | JFK         | DFW-JFK     | SFO  |  400 |   1 |
| SFO    | JFK         | JFK         | SFO  |  500 |   0 |
| JFK    | LHR         | DFW-JFK-LHR | SFO  | 1400 |   2 |
| JFK    | LHR         | JFK-LHR     | SFO  | 1500 |   1 |
| DFW    | MCO         | DFW-MCO     | SFO  |  300 |   1 |
| SFO    | MCO         | MCO         | SFO  |  400 |   0 |
+--------+-------------+-------------+------+------+-----+

db小提琴链接

https://dbfiddle.uk/?rdbms=postgres_12&fiddle=2fc63555177972cb6c60e63d030fc9af

Answer 2

由于最多只考虑两个步骤，因此可以使用union all:

select f.origin, f.destination, 0 steps, f.cost, f.origin || '->' || f.destination route
from flights f
union all
select f1.origin, f2.destination, 1, f1.cost + f2.cost, f1.origin || '->' || f1.destination || '->' || f2.destination route
from flights f1
inner join flights f2 on f1.destination = f2.origin
union all
select f1.origin, f3.destination, 2, f1.cost + f2.cost + f3.cost, f1.origin || '->' || f1.destination || '->' || f2.destination || '->' || f3.destination route
from flights f1
inner join flights f2 on f1.destination = f2.origin
inner join flights f3 on f2.destination = f3.origin
order by cost, steps

结果：

| origin | destination | steps | cost | route              |
| ------ | ----------- | ----- | ---- | ------------------ |
| DFW    | MCO         | 0     | 100  | DFW->MCO           |
| SFO    | DFW         | 0     | 200  | SFO->DFW           |
| DFW    | JFK         | 0     | 200  | DFW->JFK           |
| SFO    | MCO         | 1     | 300  | SFO->DFW->MCO      |
| SFO    | MCO         | 0     | 400  | SFO->MCO           |
| SFO    | JFK         | 1     | 400  | SFO->DFW->JFK      |
| SFO    | JFK         | 0     | 500  | SFO->JFK           |
| JFK    | LHR         | 0     | 1000 | JFK->LHR           |
| DFW    | LHR         | 1     | 1200 | DFW->JFK->LHR      |
| SFO    | LHR         | 2     | 1400 | SFO->DFW->JFK->LHR |
| SFO    | LHR         | 1     | 1500 | SFO->JFK->LHR      |

Answer 3

我最终自己解决了这个问题，George和Andronicus都给了我如何解决这个问题的想法。

最后，我想制作一个航班列表，只显示最便宜的航班，不包括更贵的航班。

WITH RECURSIVE connecting_flights AS (
SELECT origin, destination, cost, 0 AS stops
FROM flights
UNION ALL
SELECT cf.origin, f.destination, (cf.cost + f.cost) as cost, cf.stops + 1 AS stops
FROM flights f
INNER JOIN connecting_flights cf ON cf.destination = f.origin
WHERE cf.stops <= 2 and cf.origin <> f.destination
)
SELECT flights.origin, flights.destination, cf.stops, MIN(flights.cost) as total_cost
FROM connecting_flights AS flights
INNER JOIN connecting_flights AS cf ON cf.origin = flights.origin 
AND cf.destination = flights.destination
GROUP BY flights.origin, flights.destination, cf.stops, cf.cost
HAVING MIN(flights.cost) = cf.cost
ORDER BY origin, destination;