Cheapest Flights Within K Stops

Q: Какова временная сложность алгоритма Cheapest Flights Within K Stops?

Алгоритм Беллмана — Форда, ограниченный k+1 раундами, работает за время O(k · E) для E рейсов и требует O(n) дополнительной памяти для двух массивов цен. Если за раунд ничего не изменилось, в следующем раунде останутся те же цены, поэтому можно остановиться раньше.

Q: Почему алгоритм Дейкстры не работает для задачи «Самые дешёвые авиабилеты с не более чем K пересадками»?

Алгоритм Дейкстры хранит лучшую цену для каждого города и больше не возвращается к уже обработанным городам. Здесь более дорогой путь в город может оказаться полезным, если для него потребовалось меньше перелётов. Алгоритм Дейкстры снова работает с состояниями (город, использовано перелётов), что увеличивает количество состояний в k+1 раз.

Q: Сможешь решить задачу «Самые дешёвые авиабилеты с не более чем K пересадками» с помощью BFS?

Да. Уровень r содержит города, до которых можно добраться ровно за r перелётов, и цены на них. Добавляй город на следующий уровень, только если его новая цена меньше лучшей из ранее найденных для него, и остановись после k+1 уровней. Результат будет таким же, как у Bellman-Ford, но будут рассматриваться только перелёты из городов, цена которых изменилась.

СреднеКратчайшие пути Графы

+10

Есть n городов, пронумерованных от 0 до n-1, и список рейсов в одну сторону: flights[i] = [from, to, price] — это рейс из города from в город to стоимостью price.

Верните минимальную общую стоимость поездки из src в dst с не более чем k пересадками по пути, то есть не более чем k+1 рейсами. Если такой поездки не существует, верните -1.

Функция

findCheapestPrice(n: integer, flights: integer-2d-array, src: integer, dst: integer, k: integer) → integer

ninteger: количество городов
flightsinteger-2d-array: рейсы в одну сторону, каждый в формате [from, to, price]
srcinteger: город, в котором начинается поездка
dstinteger: город, в котором заканчивается поездка
kinteger: максимально допустимое количество остановок между src и dst
Возвращаетinteger: минимальная стоимость поездки не более чем с k пересадками или -1

Ограничения

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] при 0 ≤ from, to < n и from ≠ to
1 ≤ price ≤ 10⁴
Ни у каких двух рейсов не совпадают одновременно from и to.
0 ≤ src, dst < n и src ≠ dst
0 ≤ k < n

Примеры

Ввод: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Вывод: 230
Пояснение: Одна пересадка допускает два перелёта: 0 → 1 → 3 стоит 50 + 180 = 230, а 0 → 2 → 3 стоит 200 + 50 = 250. Более дешёвый маршрут 0 → 1 → 2 → 3 включает две пересадки.

Ввод: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Вывод: 150
Пояснение: Две остановки позволяют совершить три перелёта, поэтому теперь разрешён маршрут 0 → 1 → 2 → 3, и он стоит 50 + 50 + 50 = 150.

Дополнительный вопрос

Как вернуть города, входящие в самую дешёвую поездку, а также её цену?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Это задача о кратчайшем пути с ограничением на количество перелётов. Алгоритм Дейкстры только по городам не подходит, потому что самый дешёвый путь до города может израсходовать пересадки, необходимые для оставшейся части пути. Алгоритм Беллмана — Форда учитывает это ограничение: на раунде r находится минимальная стоимость пути не более чем с r перелётами, поэтому нужно выполнить k+1 раундов.

Попробуйте каждый маршрут с не более чем k+1 перелётами

Верно, но не успевает на самых больших тестах

Идея

Пройдите по каждому маршруту из src, используя стек из (города, цены, количества использованных рейсов). Маршрут, достигающий dst, записывает свою цену и завершается, поскольку каждая цена положительна. Маршрут с k+1 рейсами пропускается; любой другой продолжается всеми рейсами из его города. Строится каждая допустимая поездка, поэтому минимальная записанная цена будет правильной.

Количество маршрутов растёт как d в степени k+1, где d — число рейсов из города. При 4 рейсах из каждого города и k = 29 это 4^30 ≈ 1.2 × 10^18 маршрутов.

Алгоритм

Сгруппируй рейсы по городу отправления.
Добавь в стек (src, 0, 0): город, текущую стоимость и количество совершённых перелётов.
Извлеки маршрут. Если его город — dst, сохрани его стоимость, если она пока лучшая.
Иначе, если количество совершённых перелётов меньше k+1, добавь по одному более длинному маршруту для каждого рейса из этого города.
Когда стек опустеет, верни лучшую стоимость или -1, если ни один маршрут не достиг dst.

def findCheapestPrice(n, flights, src, dst, k):
    out = [[] for _ in range(n)]
    for a, b, price in flights:
        out[a].append((b, price))
    best = -1
    # Each entry is a route in progress: (city, price so far, flights taken).
    stack = [(src, 0, 0)]
    while stack:
        city, cost, used = stack.pop()
        if city == dst:
            if best == -1 or cost < best:
                best = cost
            continue
        # k stops allow at most k+1 flights.
        if used == k + 1:
            continue
        for nxt, price in out[city]:
            stack.append((nxt, cost + price, used + 1))
    return best

Алгоритм Беллмана — Форда, ограниченный k+1 раундами

Идея

Пусть cost[c] — минимальная цена, за которую можно добраться до города c не более чем за r перелётов. При r = 0 достижим только src, и цена равна 0. Поездка в a не более чем за r перелётов, а затем перелёт a → b — это поездка в b не более чем за r+1 перелётов, поэтому на каждом раунде для каждого перелёта предлагается цена cost[a] + price для города b. После k+1 раундов cost[dst] — это ответ.

На каждом раунде используются цены предыдущего раунда, а результаты записываются в копию, поэтому цена, установленная в течение раунда, не может стать основой для другого перелёта в том же раунде. В первом примере при k = 1 цена до города 2 снижается до 100 во втором раунде, но раундов уже не остаётся, чтобы продолжить путь до города 3 за 150.

В каждом раунде каждый перелёт просматривается один раз: время O(k · E) для E перелётов, а память O(n) для двух массивов.

Алгоритм

Установите cost[src] = 0, а все остальные значения cost — равными бесконечности.
Повторите k+1 раз: скопируйте cost в next.
Для каждого рейса [a, b, price], для которого cost[a] конечно, если cost[a] + price < next[b], установите next[b] = cost[a] + price.
Замените cost на next и остановитесь раньше, если ничего не изменилось.
Верните cost[dst] или -1, если оно всё ещё равно бесконечности.

def findCheapestPrice(n, flights, src, dst, k):
    INF = float("inf")
    # cost[c]: the cheapest price to reach city c with the flights allowed so far.
    cost = [INF] * n
    cost[src] = 0
    # Each round allows one more flight; k stops means k+1 flights.
    for _ in range(k + 1):
        # Read last round's prices and write into a copy,
        # so one round can never chain two flights.
        nxt = cost[:]
        changed = False
        for a, b, price in flights:
            if cost[a] != INF and cost[a] + price < nxt[b]:
                nxt[b] = cost[a] + price
                changed = True
        cost = nxt
        if not changed:
            break
    return -1 if cost[dst] == INF else cost[dst]

Ловушки и крайние случаи

Подсчёт пересадок как перелётов. k пересадок означают k+1 перелётов и k+1 раундов.
Обновление на месте. При 0 → 1, 1 → 2, 2 → 3 стоимостью 1 каждый, именно в таком порядке, а также 0 → 3 стоимостью 500 и k = 0, за один раунд выполняются три перелёта по цепочке, и результат равен 3, а не 500.
Запуск обычного алгоритма Дейкстры на городах. При 0 → 1 и 1 → 2 стоимостью 1 каждый, 0 → 2 стоимостью 40, 2 → 3 стоимостью 1 и k = 1 алгоритм фиксирует расстояние до города 2, равное 2, после двух перелётов и пропускает маршрут 0 → 2 → 3 стоимостью 41.
Вылет из недостигнутого города. Если бесконечность представлена максимальным значением типа int, то cost[a] + price переполняется и становится отрицательным числом в 32-битном представлении. Сначала проверьте, что cost[a] конечно.

Частые вопросы3

Какова временная сложность алгоритма Cheapest Flights Within K Stops?

Алгоритм Беллмана — Форда, ограниченный k+1 раундами, работает за время O(k · E) для E рейсов и требует O(n) дополнительной памяти для двух массивов цен. Если за раунд ничего не изменилось, в следующем раунде останутся те же цены, поэтому можно остановиться раньше.

Почему алгоритм Дейкстры не работает для задачи «Самые дешёвые авиабилеты с не более чем K пересадками»?

Алгоритм Дейкстры хранит лучшую цену для каждого города и больше не возвращается к уже обработанным городам. Здесь более дорогой путь в город может оказаться полезным, если для него потребовалось меньше перелётов. Алгоритм Дейкстры снова работает с состояниями (город, использовано перелётов), что увеличивает количество состояний в k+1 раз.

Сможешь решить задачу «Самые дешёвые авиабилеты с не более чем K пересадками» с помощью BFS?

Да. Уровень r содержит города, до которых можно добраться ровно за r перелётов, и цены на них. Добавляй город на следующий уровень, только если его новая цена меньше лучшей из ранее найденных для него, и остановись после k+1 уровней. Результат будет таким же, как у Bellman-Ford, но будут рассматриваться только перелёты из городов, цена которых изменилась.

def findCheapestPrice(n, flights, src, dst, k):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

n = 4
flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]
src = 0
dst = 3
k = 1

Ожидаемый вывод