时间戳

首页 > 解决方案 > 创建查询以查找少于三个停靠点的目的地之间最便宜的路线

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

问题描述

直飞城市到城市的航班通常比在枢纽城市中途停留的两次航班更昂贵。

旅行者可以通过将旅行分为三个航班和两个站点来节省更多的钱。

您有一个包含各个机场到机场航班的表格，其中包含以下列：

我们必须创建一个查询或程序，列出所有可以在两站或更少站内完成的最便宜的旅行。输出应包含起点、目的地、停靠点（指示当前行程中的停靠点数）和总成本列。

如果两次旅行的费用相同但停靠次数不同，则包括停靠次数最少的一次。

按起点对输出表进行排序，然后按目的地排序。

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

示例对于给定的餐桌航班

|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     |

我能做的可以在这个链接上找到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 //

标签： mysqlsqlstored-procedures

解决方案

检查这个：

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;

小提琴

我忘了提到我们必须通过这个存储过程返回数据 CREATE PROCEDURE get_cheapest_flights() BEGIN QUERY END // – Rajeev.Massey

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

我只需要两地之间最便宜的航班——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;

小提琴

推荐阅读