Модуль 21 ⏱ ~13 мин чтения 📐 1 Mermaid диаграмм

9. Cheapest Flights Within K Stops

«Оптимальность — это не просто минимальная стоимость, это поиск лучшего компромисса в жестких границах реальности».
— Ричард Беллман

Бизнес-ограничения в маршрутизации

В задаче 8. Network Delay Time мы находили абсолютный кратчайший путь с помощью алгоритма Дейкстры. Однако в прикладной инженерии чистая математика сталкивается с жесткими бизнес-ограничениями.

Пользователю не нужен самый дешевый билет, если ради экономии придется совершить $5$ пересадок и провести в пути двое суток. В системах бронирования (GDS Sabre, Amadeus) и в сетевых прокси-балансировщиках (где каждый дополнительный хоп увеличивает риск потери пакета и джиттер) строго задается лимит промежуточных узлов (Hop Limit).

Задача Cheapest Flights Within K Stops (LeetCode №787) моделирует именно такой сценарий:

Условие: Задано $n$ городов и массив авиарейсов flights, где flights[i] = [from, to, price]. Требуется найти наименьшую стоимость перелета из города src в город dst, совершив не более $K$ пересадок (то есть не более $K + 1$ перелета). Если маршрут в рамках ограничения не существует, вернуть -1.

Почему классический алгоритм Дейкстры терпит крах?

Жадные алгоритмы типа Дейкстры минимизируют единственную метрику (стоимость). В базовом виде алгоритм найдет абсолютно дешевый маршрут, но тот вполне может потребовать $K + 5$ пересадок.

flowchart LR
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc

    A["A (Старт)"]:::entry -->|"Прямой: 100$"| D["D (Финиш)"]:::success
    A -->|"10$"| B["B"]:::process
    B -->|"10$"| C["C"]:::process
    C -->|"10$"| D

Пример при $K = 0$ (прямой рейс без пересадок):
Классический Дейкстра первым делом пойдет по цепочке $A \rightarrow B \rightarrow C \rightarrow D$ (суммарно $30\$$). На шаге $C \rightarrow D$ выяснится, что лимит пересадок исчерпан. Однако к этому моменту прямой рейс $A \rightarrow D$ ($100\$$) мог быть отброшен или узел $D$ помечен как окончательно исследованный.

Чтобы адаптировать Дейкстру, придется хранить в куче кортеж (цена, узел, число_пересадок), а массив расстояний расширять до матрицы dist[node][stops]. Это усложняет алгоритм и увеличивает накладные расходы памяти.
Гораздо естественнее использовать алгоритмы, квантующие обход по уровням.

Подход 1: Поуровневый BFS (Поиск в ширину)

Обход графа по уровням (Level-Order Traversal) идеально транслируется на ограничение пересадок: один уровень BFS равен ровно одному перелету. Глубина поиска ограничивается циклом на $K + 1$ итераций.

package main

import "math"

// findCheapestPriceBFS решает задачу поуровневым BFS.
func findCheapestPriceBFS(n int, flights [][]int, src int, dst int, k int) int {
    type Edge struct {
        to    int
        price int
    }

    graph := make([][]Edge, n)
    for _, f := range flights {
        u, v, w := f[0], f[1], f[2]
        graph[u] = append(graph[u], Edge{to: v, price: w})
    }

    minCost := make([]int, n)
    for i := range minCost {
        minCost[i] = math.MaxInt32
    }
    minCost[src] = 0

    type State struct {
        node int
        cost int
    }
    queue := []State{{node: src, cost: 0}}

    // Совершаем не более K + 1 перелетов
    for stops := 0; stops <= k && len(queue) > 0; stops++ {
        levelSize := len(queue)

        for i := 0; i < levelSize; i++ {
            curr := queue[0]
            queue = queue[1:]

            for _, edge := range graph[curr.node] {
                nextCost := curr.cost + edge.price

                // Отсекаем неэффективные пути
                if nextCost < minCost[edge.to] {
                    minCost[edge.to] = nextCost
                    queue = append(queue, State{node: edge.to, cost: nextCost})
                }
            }
        }
    }

    if minCost[dst] == math.MaxInt32 {
        return -1
    }
    return minCost[dst]
}

Подход 2: Алгоритм Беллмана-Форда (Bellman-Ford)

Классический алгоритм Беллмана-Форда находит кратчайшие пути, релаксируя все ребра графа $V - 1$ раз.
Его фундаментальное свойство: после $i$-й итерации алгоритм гарантированно находит кратчайшие пути, содержащие не более $i$ ребер.

Это свойство идеально ложится на условие нашей задачи: нам требуется выполнить ровно $K + 1$ итераций релаксации. При этом нам даже не нужен список смежности — мы оперируем напрямую исходным срезом flights.

Подводные камни / Gotcha

Ловушка / Gotcha: Чтение обновленных данных в текущей итерации (Read-after-Write)
Допустим, имеются ребра $A \rightarrow B$ и $B \rightarrow C$.
Если на текущем шаге мы обновили расстояние до $B$, а затем в том же проходе обновили $C$ на основе нового значения $B$, мы за одну итерацию совершили $2$ перелета! Это прямое нарушение лимита $K$.
Решение: использовать два массива расстояний. Срез dist фиксирует состояние предыдущего шага (только чтение), а срез temp накапливает релаксации текущего шага.

Production-Ready реализация (Mechanical Sympathy)

package main

import "math"

// findCheapestPrice находит минимальную стоимость авиаперелета с не более K пересадками
// алгоритмом Беллмана-Форда с изоляцией шагов релаксации.
// Временная сложность: O(K * E), где E — количество рейсов.
// Пространственная сложность: O(V) для двух плоских массивов цен.
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    const Inf = math.MaxInt32

    dist := make([]int, n)
    for i := range dist {
        dist[i] = Inf
    }
    dist[src] = 0

    // Временный массив для изоляции итераций
    temp := make([]int, n)

    // Ровно K + 1 шагов релаксации
    for i := 0; i <= k; i++ {
        // copy() выполняет быстрое побайтовое копирование на уровне CPU memmove
        copy(temp, dist)

        for _, flight := range flights {
            u, v, price := flight[0], flight[1], flight[2]

            if dist[u] != Inf && dist[u]+price < temp[v] {
                temp[v] = dist[u] + price
            }
        }

        copy(dist, temp)
    }

    if dist[dst] == Inf {
        return -1
    }
    return dist[dst]
}

Mechanical Sympathy: Архитектурные преимущества Беллмана-Форда

Непрерывность памяти: Мы работаем с плоскими срезами []int. Никаких структур с указателями и сборщика мусора.
Аппаратный Prefetching: Цикл for _, flight := range flights идет строго линейно. Аппаратный блок процессора Hardware Prefetcher заранее подтягивает данные из оперативной памяти в кэш первого уровня L1.
Zero Allocations в цикле: Память под dist и temp выделяется ровно один раз. Функция copy() выполняет копирование блоками машинных слов без аллокаций.

Резюме

Многокритериальная оптимизация: Когда кратчайший путь ограничен числом ребер, поуровневый BFS и Беллман-Форд предпочтительнее алгоритма Дейкстры.
Изоляция шагов: В алгоритме Беллмана-Форда с ограничением на число шагов обязательна буферизация предыдущего состояния через temp, иначе произойдет преждевременная релаксация нескольких звеньев за один цикл.
Эффективность памяти: Вариант Беллмана-Форда требует всего $O(V)$ памяти и работает без построения списка смежности.

На этом мы завершаем разбор графовых структур данных и переходим к следующему фундаментальному блоку — системам непересекающихся множеств: 1. Теория. Union Find.