Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘787. Самые дешевые рейсы в пределах K остановок». Вопрос с расширенным графиком.

Вопрос:

Есть n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] обозначает, что существует рейс из города from в city to со стоимостью price.

Вам также даны три целых числа src, dst и k, верните самую дешевую цену от src до dst с не более чем k остановками. Если такого маршрута не существует, верните -1.

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Войти в полноэкранный режим Выйти из полноэкранного режима

Объяснение вопроса

Этот вопрос оценивается как средний. Я бы сказал, что это неточно, даже если вы знаете Bellman-Ford или Dijkstra, у вас все равно будут проблемы с решением этого вопроса, особенно если вы используете Dijkstra, потому что ограничения Leetcode Runtime очень строгие. Из-за того, насколько строг этот вопрос, я бы сказал, что это трудный вопрос, если вы используете Dijkstra, и средний, если используете Bellman-Ford. Для решения этого вопроса мы будем использовать Dijkstra.

Дийкстра — это жадный алгоритм, который находит кратчайший путь от источника к пункту назначения. Его работа во многом похожа на поиск по принципу Breadth First Search. Мы собираемся найти самые дешевые рейсы из src в dst в пределах k остановок.

Как, по-вашему, Google Maps знает кратчайший путь (расстояние Be или стоимость) между вашим домом и аэропортом Нью Йорк? Алгоритмы кратчайшего пути, такие как алгоритм Дейкстры или алгоритм Беллмана-Форда, используются для поиска кратчайшего пути между двумя точками.

Что мы знаем?

Нам дан массив [flights], где flights[i] = [from, to, price] указывает, что существует рейс из города from в city to со стоимостью price. Что можно представить в виде списка смежности.
Нам нужно добраться от src до dst за k остановок. Где мы ищем самый дешевый перелет между src и dst в пределах k остановок.

Как мы собираемся это сделать:

Мы будем использовать алгоритм Дейкстры для поиска кратчайшего пути между src и dst, где мы начнем с самых дешевых рейсов относительно src в порядке возрастания, пока не достигнем dst или не достигнем k остановок. Как только мы достигнем dst, мы сможем вернуть стоимость перелета относительно src.

Самое важное здесь то, что нам нужно предотвратить многократное посещение одного и того же города. Поэтому мы используем [Hashmap] для отслеживания количества остановок, которые потребовались для посещения этого города в первый раз, чтобы понять, стоит ли снова посетить этот город по другому пути.

Мы создадим очередь Priority Queue для хранения всех узлов, которые нам нужно пройти. Как и в алгоритме Дейкстры, мы будем использовать Priority Queue для хранения узлов, которые нам нужно обойти в первую очередь. (Самый дешевый рейс первым)
Мы также будем вести глобальную хэш-карту, чтобы узнать, посещали ли мы этот город раньше, и если да, то сколько остановок потребовалось, чтобы добраться до этого города, это позволит нам знать в будущем, стоит ли нам снова посетить этот город. Это означает, что он дешевле, чем наш текущий узел, и мы можем вернуться сюда.
Поскольку мы знаем, что начинаем с src, мы добавим его в Priority Queue со значением 0, потому что он нам ничего не стоил, так как мы начали отсюда, и 0 тоже останавливает.
Затем мы начнем выполнять алгоритм Дейкстры, в котором мы удаляем «самый дешевый» элемент из Min-Heap, то есть мы перебираем все самые дешевые рейсы сначала, пока они находятся в пределах k остановок. Мы также зарегистрируем количество остановок, которое потребовалось, чтобы добраться до этого города в этом наборе.
Затем мы будем постоянно исследовать самые дешевые рейсы и добавлять их в очередь приоритетов Priority Queue, пока не достигнем dst или не пройдем k остановок.

Нотация Big O:

Временная сложность: O((((V + E) * K))) | Правильно, это немного запутано. Алгоритм Дейкстры — это алгоритм O(ElogV). Где E — количество ребер в графе, а V — количество вершин в графе. Что представляется O(V^2), так как в худшем случае каждая вершина и ее соседи будут добавлены и удалены из Min-Heap несколько раз. Но так как мы ограничены K, мы собираемся ограничиться K остановками, поэтому мы собираемся ограничиться K * V * E операциями. Поэтому в амортизированной форме это O((V + E) * K). В худшем случае мы можем представить это как O((V^2)).
Пространственная сложность: O(V + E)| Как и в худшем случае, мы будем хранить весь граф в нашей Min-Heap или в нашем посещенном множестве.

Может быть, мой анализ неверен? Возможно, не стесняйтесь меня поправить. 😁

Результаты Leetcode:

См. ссылку на представление:

Решение

const findCheapestPrice = function (n, flights, src, dst, K) {

    // Firstly build an Adjacency List
    // City => [[Out-City, Cost], [Out-City, Cost], ...]
    const node_edge_cost = new Map();
    for (const [from, to, price] of flights){
        let edges = [];
        if (node_edge_cost.has(from)){
            edges = node_edge_cost.get(from);
        }
        edges.push([to, price])
        node_edge_cost.set(from, edges)
    }

    // Dijkstra's Algorithm in this case uses a min-heap to store the cheapest paths.
    const min_heap = new MinPriorityQueue();

    // We also have a distance from K memo.
    // As it's entirely possible to revisit a node again, so it's useful to 
    // know it's distance from K. So we can know if it's worth even visiting it. 
    const distance_from_k_memo = new Map();

    // We want to start of with the provided source node.
    // It's distance from DST is set to the maximum value it
    // can possibly be, that being K. As we don't want to 
    // to visit a node that's too far away. So we use K to dictate that distance.
    // So once, we branch out and get to 0, and not reached K, we'll stop.
    min_heap.enqueue([src, K + 1], 0);

    // Keep running Dijkstra's Algorithm until we've reached the destination.
    // Or the min-heap is empty.
    while (min_heap.size()){

        // Get the cheapest path from the min-heap.
        // Get the price of the cheapest path.
        // And get the city and distance from DST
        const node = min_heap.dequeue();
        const price = node.priority;
        const [to, distance_from_k] = node.element;

        // Set it within the memo, just in case
        // we come across this node again in the future.
        // So we can tell if it's worth even visiting it again. 
        distance_from_k_memo.set(to, distance_from_k);

        // We've reached the cheapest path to the destination.
        // Return the price.
        if (to === dst) return price;

        // Hmm, seems like we're 0 distance from the destination / K.
        // but not at the destination, guess it's time to backtrack.
        if (distance_from_k <= 0) continue;

        // Get the outbound edges from the current node.
        const edges = node_edge_cost.get(to) || [];

        // Go through each edge and enqueue it.
        // So long as it's worth visiting (Meaning, that if we've visited it, is it 
        // cheaper than the current cheapest path?) If so we can add it back into the min-heap.
        for (const [outbound, out_cost] of edges){

            if (distance_from_k_memo.get(outbound) >= distance_from_k - 1) continue;

            // Enqueue into the min heap with updated cost and distance from K.
            min_heap.enqueue([outbound, distance_from_k - 1], out_cost + price)                
        }

    }

    // This is embarrassing, but we've reached the end of the graph 
    // and not found DST within K hops. So we return -1.
    return -1;
};

Войдите в полноэкранный режим Выход из полноэкранного режима

787. Самые дешевые авиабилеты в пределах K остановок 🚀

Решение разработано в: