Мир аналитика данных: “Подписчик прислал мне интересную задачку с stratascratch.com, и я не м…”

Подписчик прислал мне интересную задачку с stratascratch.com, и я не могла устоять, чтобы не решить её.
Нужно найти самый дешёвый путь между городами, учитывая варианты с пересадками (до двух).

📌 Дано:
Есть таблица da_flights, в которой:
✈️ origin – пункт отправления
✈️ destination – пункт назначения
✈️ cost – стоимость перелёта

Чтобы найти маршруты с пересадками, нам нужно соединить таблицу саму с собой (self-join).

🛠 Решение

1️⃣ Прямые рейсы (без пересадок) — просто берём origin, destination, cost.

2️⃣Рейсы с одной пересадкой — соединяем таблицу саму с собой (JOIN), где f1.destination = f2.origin. Это значит, что первый рейс прилетает в город, из которого отправляется второй.

3️⃣ Рейсы с двумя пересадками — соединяем таблицу трижды (JOIN), добавляя ещё один уровень соединения (f2.destination = f3.origin).

4️⃣Объединение всех маршрутов:
Используем UNION для объединения всех трех типов маршрутов (прямые, с одной и двумя пересадками).

5️⃣Группируем GROUP BY origin, destination и выбираем минимальную цену MIN(total_cost). Жаль нельзя по таким ценам реально на морюшко улететь 🌊🌊🌊

6️⃣Сортируем результат по городу отправления и городу назначения.

Создадим табличку с данными:

import pandas as pd 
from pandasql import sqldf  

data = {
    'id': [1, 2, 3, 4, 5, 6],
    'origin': ['SFO', 'SFO', 'SFO', 'DFW', 'DFW', 'JFK'],
    'destination': ['JFK', 'DFW', 'MCO', 'MCO', 'JFK', 'LHR'],
    'cost': [500, 200, 400, 100, 200, 1000]
}

da_flights = pd.DataFrame(data)

Ну и сам основной запрос:

query = """
SELECT 
    origin, 
    destination, 
    MIN(total_cost) AS min_price
FROM (
    -- Прямые рейсы
    SELECT origin, destination, cost AS total_cost        
    FROM da_flights
    UNION
    -- Рейсы с одной пересадкой
    SELECT f1.origin, f2.destination, f1.cost + f2.cost AS total_cost
    FROM da_flights f1
    JOIN da_flights f2 ON f1.destination = f2.origin
    UNION
    -- Рейсы с двумя пересадками
    SELECT f1.origin, f3.destination, f1.cost + f2.cost + f3.cost AS total_cost
    FROM da_flights f1
    JOIN da_flights f2 ON f1.destination = f2.origin
    JOIN da_flights f3 ON f2.destination = f3.origin
) AS all_flights
GROUP BY origin, destination
ORDER BY origin, destination
"""

result = sqldf(query)
print(result)

Большое решение, но если по частям разобрать, то разобраться проще. Для этого вот вам ноутбук с этим скриптом. экспериментируйте!
Ну и всем отдыха на море в этом году! 🏖🏖🐠🌊