솔루션 개발:

질문

이 기사에서는 Leetcode의 '743. Network Delay Time' 질문을 다룰 것입니다. 고급 그래프 질문입니다.

의문:

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

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

질문 설명

이 질문의 등급은 보통입니다. Dijkstra's Algorithm 또는 Bellman-Ford's Algorithm 또는 기타 경로 찾기 알고리즘에 익숙하다면 정확하다고 말하고 싶습니다. 대부분의 사람들은 고등 교육에서 이 알고리즘을 공부할 것입니다. 그러나 당신이 나와 같다면 고등 교육을 받지 않았다는 것은 내가 그래프에서 Path Finding Algorithms에 대해 조금도 알지 못했다는 것을 의미하지 않습니다. 나를 위해 나는이 질문이 Dijkstra's Algorithm에 의해 해결되었다는 것을 읽을 때까지 해결할 수 없다는 것을 알았습니다.

우리는 그래프를 받았고 전체 그래프를 순회하고 최단 경로를 사용하여 모든 노드에 도달하도록 요청받습니다. Kruskal's Algorithm 과 많이 비슷하지만 k와 다른 모든 노드 사이에 Minimum Spanning Tree이 아니라 Shortest Path이 생성됩니다.

Google Maps이 당신의 집과 친구 집 사이의 최단 거리를 어떻게 안다고 생각하세요? Shortest Path 또는 Dijkstra's Algorithm과 같은 Bellman-Ford's Algorithm 알고리즘은 두 위치 사이의 최단 경로를 찾는 데 사용됩니다.

정확히 우리가 할 일입니다. k와 다른 모든 노드 사이의 최단 경로 찾기.

권장 지식

Graph Theory

Dijkstra's Algorithm

Hashmap

Adjacent List

Path Finding Algorithms

Priority Queue

Heap

우리는 무엇을 알고 있습니까?

연결이 있는 노드 목록과 비용이 제공됩니다.

노드에 인바운드 연결이 없을 수 있으므로 이 경우 {k}에서 모든 노드에 도달하는 것이 불가능하므로 -1을 반환해야 합니다

.

어떻게 할 것인가:

Dijkstra's Algorithm을 사용하여 k와 다른 모든 노드 사이의 최단 경로를 찾을 것입니다.

먼저 인접 목록(노드 -> [에지, 비용])을 생성합니다. 이렇게 하면 그래프에서 모든 연결 및 비용을 알 수 있습니다. 여기에서 비어 있는 노드Minumum Priority Queue를 생성하고 여기에서 시작할 때 비용이 0인 첫 번째 노드를 대기열에 추가합니다.

그런 다음 while 루프를 사용하여 큐가 비워질 때까지 루프를 계속 돌면서 최소 힙을 팝하여 항상 가능한 다음 최단 경로를 제공합니다. 이 노드를 사용하여 새 노드 가장자리를 min-heap에 계속 추가하고 노드 비용을 업데이트합니다.

노드 비용을 업데이트하는 이유는 입력 노드에서 {k}에 상대적으로 이동하기 때문입니다. 최단 경로는 {k}에서 바깥쪽으로 캐스케이드됨을 의미합니다. 그래프 내의 모든 노드를 방문할 때까지 노드에 최단 경로를 계속 추가하고 최소 힙에 가장자리를 추가합니다. Set을 사용하여 방문한 노드를 추적하기 때문에 모든 노드를 방문했음을 알 수 있습니다.

노드를 이동할 때마다 전역 시간 변수를 업데이트합니다. 시간이 {k}에 비해 증가한 경우 에지 비용만큼 증가합니다.

빅오 표기법:

시간 복잡도: O(V^2) | 각 정점이 다른 모든 정점에 연결되는 것이 전적으로 가능하기 때문입니다. 따라서 잠재적으로 모든 정점을 여러 번 방문할 수 있습니다. 우리 세트는 처리하지 않도록 합니다.

공간 복잡도: O(V^2) | 작업을 힙에 저장할 것입니다.

Dijkstra's Algorithm의 시간 및 공간 복잡성은 매우 혼란스럽기 때문에 이 특정 질문에 대해 Min-heap을 사용하여 Dijkstra의 알고리즘에 대한 분석을 자유롭게 수정하십시오. 복잡성을 파악할 때 모든 노드가 자신을 제외한 모든 노드에 연결되는 그래프를 상상했습니다.

리트코드 결과:

제출 링크 참조:

해결책

/**
 * @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;
};