Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘743. Время задержки в сети». Вопрос с расширенным графиком.

Вопрос:

Вам дана сеть из n узлов, обозначенных от 1 до n. Вам также даны времена, список времен путешествия times в виде направленных ребер times[i] = (ui, vi, wi), где ui — исходный узел, vi — целевой узел, и wi — время, необходимое сигналу для путешествия от источника к цели.
Мы пошлем сигнал из заданного узла k. Верните минимальное время, необходимое всем узлам n для получения сигнала. Если невозможно, чтобы все n узлов получили сигнал, верните -1.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

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

Этот вопрос оценивается как средний. Я бы сказал, что это верно, если вы знакомы с алгоритмом Дейкстры, алгоритмом Беллмана-Форда или любым другим алгоритмом поиска пути. Большинство людей изучают этот алгоритм в высших учебных заведениях. Но если вы похожи на меня, то, не получив высшего образования, я не имел ни малейшего представления об алгоритмах поиска пути в графе. Для меня этот вопрос казался неразрешимым, пока я не прочитал, что он был решен алгоритмом Дейкстры.

Нам дан граф, и нас просят пройти весь граф и добраться до всех узлов по кратчайшему пути. Это очень похоже на алгоритм Крускала, только мы создаем не минимальное прячущееся дерево, а кратчайший путь между k и всеми остальными узлами.

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

Именно это мы и собираемся сделать. Найдем кратчайший путь между k и всеми остальными узлами.

Что мы знаем?

Нам дан список узлов с соединением и его стоимость.
Возможно, что у узла нет входящих соединений, и в этом случае мы должны вернуть -1, поскольку невозможно достичь всех узлов из {k}.

Как мы это сделаем:

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

Во-первых, мы создадим себе список смежности (Node -> [Edge, Cost]). Мы делаем это для того, чтобы знать все соединения и затраты в графе. Отсюда мы генерируем пустую очередь с минимальным приоритетом и добавляем в нее первый узел со стоимостью 0, так как мы начинаем с этого.

Затем мы будем использовать цикл while, чтобы продолжать цикл до тех пор, пока очередь не станет пустой, где мы выберем min-heap, который всегда будет давать нам следующий кратчайший возможный путь. С этим узлом мы будем продолжать добавлять ребра этого нового узла в min-heap и обновлять стоимость узла.

Причина, по которой мы обновляем стоимость узла, заключается в том, что мы перемещаемся относительно {k}, входного узла. Это означает, что кратчайший путь каскадирует наружу от {k}. Мы продолжаем добавлять кратчайший путь к узлу и его ребрам в min-кучу, пока не посетим все узлы графа. Мы знаем, что посетили все узлы, потому что используем множество для отслеживания того, какие узлы мы посетили.

Каждый раз, когда мы перемещаем узел, мы обновляем глобальную переменную времени. Если время увеличилось относительно {k}, мы увеличиваем его на стоимость ребра.

Нотация Big O:

Временная сложность: O(V^2)| Поскольку вполне возможно, что каждая вершина соединена с каждой другой вершиной. Таким образом, потенциально мы можем посетить каждую вершину несколько раз. Хотя наш набор гарантирует, что они не будут обрабатываться.
Пространственная сложность: O(V^2)| Поскольку мы собираемся хранить операции в куче.

Временная и пространственная сложность алгоритма Дейкстры очень запутаны, поэтому не стесняйтесь поправить мой анализ алгоритма Дейкстры с использованием Min-кучи для этого конкретного вопроса. При расчете сложности я представлял себе граф, в котором каждый узел соединен с каждым узлом, кроме самого себя.

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

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

Решение

/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {


    // Our return value, how long did it take
    // to reach all nodes within the network from {k}
    let time_taken = 0;

    // A set so we don't visit the same node twice.
    const visited_set = new Set();

    // A min heap, as we want to visit the the node
    // with the cheapest path so far. Relative to {k}.
    // See: https://github.com/datastructures-js/priority-queue
    // Heaps are built into Leetcodes Runtime for JavaScript. 😁😁
    const min_heap = new MinPriorityQueue();

    // An adjacency list, where we store 
    // Node -> [[Edge, Cost],[Edge, Cost]]
    const node_edge_cost = new Map();

    // Build the adjacency list.
    for (const [node, edge, cost] of times) {
        let edges = [];
        if (node_edge_cost.has(node)) {
            edges = node_edge_cost.get(node);
        }
        edges.push([edge, cost]);
        node_edge_cost.set(node, edges);
    }

    // We have been asked to start at {k}
    // So we enqueue {k} at the cost of 0, as of course
    // it costs nothing as we start here.
    min_heap.enqueue([k, 0], 0);

    // Perform Dijkstra's algorithm.
    // Get the cheapest operation relative to {k}
    // and add it's edges to the heap, where we're always
    // updating the cost relative to {k}. Therefore, 
    // we're visiting all the cheapest operations relative to {k}.
    while (min_heap.size()) {

        // Get the cheapest operation relative to {k}
        // Node and cost
        const [node, cost] = min_heap.dequeue().element;

        // Have we already been here? No loops today kiddo
        if (visited_set.has(node)) continue;

        // Set it. We don't want to come back here. 
        visited_set.add(node);

        // Did our distance increase?
        // If so, update it. If not, keep the same
        time_taken = Math.max(cost, time_taken);

        // Get the edges for this node (If any)
        const node_edges = node_edge_cost.get(node) || [];

        // Get all the edges for this node and add them to the heap
        // If they haven't been visited yet. Note:
        // We're adding the cost of the given nde to the cost of the edge.
        // Because we're moving out relative to {k}. Thus,
        // even if all nodes have a cost of 2.
        // It's going to cascade outwards.
        // 2 -> 4 -> 6 -> 8 etc.
        for (const [edge_node, edge_cost] of node_edges) {
            if (!visited_set.has(edge_node)) {

                // Add it to the queue, set the priority to the cost of the edge
                // So we only ever visit the cheapest edge.
                min_heap.enqueue([edge_node, edge_cost + cost], edge_cost + cost);
            }
        }
    }

    // Did we visit every node?
    // If not, we failed to spread the message across the network.
    // If so, return the time taken. 
    return visited_set.size === n ? time_taken : -1;
};