创建查询以查找目的地之间停靠点少于三个的最便宜路线

Question

直达城市的航班通常比在枢纽城市经停的两次航班更贵。

如果将行程分成三个航班，停两站，旅客可能会节省更多的钱。

您有一个 table 单独的机场到机场航班，其中包含以下列：

id - 航班的唯一ID；
origin - 的起源城市当前航班；
destination - 当前的目的地城市飞行;
cost - 当前航班的费用。

我们必须创建一个查询或过程，列出所有可以在两站或更少站内完成的最便宜的可能旅行。输出应包含 origin、destination、stops（表示当前行程中的停靠点数）和 total_cost.

列

如果两次行程费用相同但停靠站数不同，请包括停靠站最少的那趟。

将输出 table 按来源排序，然后按目的地排序。

注意：从 SFO 到 JFK 的航班被认为不同于从 JFK 到 SFO 的航班。

例子对于给定的 table 个航班

|id| origin | destination | cost |
|--+--------+-------------+------|
| 1|   SFO  |    JFK      |  500 |
| 2|   SFO  |    DFW      |  200 |
| 3|   SFO  |    MCO      |  400 |
| 4|   DFW  |    MCO      |  100 |
| 5|   DFW  |    JFK      |  200 |
| 6|   JFK  |    LHR      | 1000 |

输出应该是

| origin | destination | stops | total_cost |
|--------|-------------|-------|------------|
|  DFW   |    JFK      |   0   |    200     | 
|  DFW   |    LHR      |   1   |   1200     |
|  DFW   |    MCO      |   0   |    100     | 
|  JFK   |    LHR      |   0   |   1000     | 
|  SFO   |    DFW      |   0   |    200     |
|  SFO   |    JFK      |   1   |    400     |
|  SFO   |    LHR      |   2   |   1400     |
|  SFO   |    MCO      |   1   |   3000     |

我能做的可以在这个 link https://www.db-fiddle.com/f/2djkYh2zKb9nzUQYaWNCrn/1

上找到

这些是我的查询运行

CREATE TABLE flights (id int,origin varchar(3),destination varchar(3),cost int);
insert into flights values
(1,'SFO','JFK',500),
(2,'SFO','DFW',200),
(3,'SFO','MCO',400),
(4,'DFW','MCO',100),
(5,'DFW','JFK',200),
(6,'JFK','LHR',1000);


select a.origin,b.destination,sum(b.destination) as stops,
MIN(ifnull(a.cost, 0) + ifnull(b.cost, 0)) as total_cost from flights a 
cross join flights b
group by   origin,   destination

我的输出与要求的相去甚远。我也对外部连接进行了同样的尝试，但仍然无法达到预期的结果。结果必须通过定义为

的存储过程返回

CREATE PROCEDURE get_cheapest_flights()
BEGIN
    QUERY
END //

Answer 1

检查这个：

WITH RECURSIVE
cte AS ( SELECT origin, 
                destination, 
                cost, 
                CAST(id AS CHAR) path, 
                0 stops_count
         FROM flights
       UNION ALL
         SELECT cte.origin, 
                flights.destination, 
                cte.cost + flights.cost,
                CONCAT(cte.path, ',', flights.id), 
                cte.stops_count + 1
         FROM cte
         JOIN flights ON cte.destination = flights.origin 
                     AND !FIND_IN_SET(flights.destination, cte.path)
                     AND cte.stops_count < 2 )
SELECT * 
FROM cte
ORDER BY 1,2,3,5;

fiddle

I forgot to mention the that we have to return the data though this stored procedure CREATE PROCEDURE get_cheapest_flights() BEGIN QUERY END // – Rajeev.Massey

解决方案是单个查询 - 因此 BEGIN-END 将其转换为存储过程时不需要重新分配定界符。

i only require the cheapest flights between two places – Rajeev.Massey

CREATE PROCEDURE get_cheapest_flights()
WITH RECURSIVE
cte AS ( SELECT origin, 
                destination, 
                cost, 
                CAST(id AS CHAR) path, 
                0 stops_count
         FROM flights
       UNION ALL
         SELECT cte.origin, 
                flights.destination, 
                cte.cost + flights.cost,
                CONCAT(cte.path, ',', flights.id), 
                cte.stops_count + 1
         FROM cte
         JOIN flights ON cte.destination = flights.origin 
                     AND !FIND_IN_SET(flights.destination, cte.path)
                     AND cte.stops_count < 2 ),
cte2 AS (SELECT *, 
                RANK() OVER (PARTITION BY origin, destination 
                             ORDER BY cost, stops_count) rnk
         FROM cte)
SELECT origin, destination, cost, path, stops_count 
FROM cte2
WHERE rnk = 1
ORDER BY 1,2,3,5;

fiddle

创建查询以查找目的地之间停靠点少于三个的最便宜路线

Create a query to find the cheapest route between destinations with fewer than three stops

mysql

sql

stored-procedures