The problem is Network Delay Time. Starting from source node, we need to return the minimum time to reach all other nodes.

The brute force way - BFS

We can use BFS approach to brute force this problem.

We know that, with BFS, starting from source node, we can reach to all other connected nodes. The problem is, how we handle the cycle problem. For a standard BFS, when we reach a node we have seen before, we can just skip it to avoid infinity loop. But we can't do that in there. Because in this problem, this is a weighted graph. It takes different time between 2 nodes. So when we reach a node which we have seen before, even though this second access happens later, it may takes shorter time.

So, in this case, what we need to do is use a map to store shortest time to reach current node. For example, if this map is an array, visited[3] = 5 means currently it takes time 5 to reach node 3. Whenever we find a shorter value, we need to update it. And then we need also run BFS on this node again, because this node's shortest time has been updated, and any other node's shortest time could be updated according to this.

So with this process, let's see the code.

function networkDelayTime(times: number[][], n: number, k: number): number {
    // node number from 1-n, to use index as node number, so minus 1 here
    const aj = Array.from({ length: n }, _ => ([] as number[][]));
    for (const time of times) {
        const [u, v, w] = time;
        aj[u - 1].push([v - 1, w]);
    }

    // queue contains source node as starting point
    let queue = [k - 1];

    // visited index stands for node number, value stands for shortest time to reach this node
    const visited = Array.from({ length: n }, _ => Number.MAX_SAFE_INTEGER);
    visited[k - 1] = 0;

    while (true) {
        const curNode = queue.shift();
        if (curNode === undefined) break;

        for (const item of aj[curNode]) {
            const [nextNode, travelTime] = item;
            const nextTime = visited[curNode] + travelTime;
            if (visited[nextNode] <= nextTime) continue;

            // nextTime is shorter, then update its value, run bfs on it again
            visited[nextNode] = nextTime;
            queue.push(nextNode);
        }
    }

    let maxTime = 0;
    for (const time of visited) {
        if (time === Number.MAX_SAFE_INTEGER) return -1;
        if (time > maxTime) {
            maxTime = time;
        }
    }
    return maxTime;
}

Dijkstra's algorithm

As you saw from above BFS approach, we may run BFS on the same node many times if current time is shorter. Dijkstra's algorithm is an algorithm for finding shortest path between nodes. It can be used to solve this problem and with it we only need to access each node once.

Like in BFS, we still starts with an array, which contains the source node. But there are 2 differences:

• array should be a min heap
• instead of only source node, but with current time takes to reach this node

Then for each iteration, we pop a value from heap, it's the node with minimum time in the heap. Then we push its neighbor nodes and the time takes to reach this node into the min heap.

In Dijkstra, we only need to access each node once, there is no update on shortest time like BFS. But the process is still like BFS, we still may push the same node into the min heap multiple times. So we need to a set to rule out the same node, if we pop out a node we have seen before, just drop it.

But why heap here? Because in Dijkstra, we need to pop out the node which have the minimum time. If we use a normal array, then it will take O(n) time to get it. If we use a min heap, then we can get it in O(1). If you are not familiar with heap, check my previous article.

So the key idea of Dijkstra algorithm is, for each iteration, instead of choosing element by appending order, we choose the one with the minimum time. So for each iteration, we choose the best option first, so we can reach the target sooner than plain BFS.

Now let's see the code.

// [node, weight]
type Val = [number, number];

class heapq {
    public static heapify(nums: Val[]) {
        for (let i = nums.length - 1; i >= 0; i--) {
            heapq._heapify(nums, i);
        }
    }

    public static heappush(nums: Val[], val: Val) {
        nums.push(val);
        heapq._swapWithParent(nums, nums.length - 1);
    }

    public static heappop(nums: Val[]): Val {
        const res = nums[0];
        nums[0] = nums[nums.length - 1];
        nums.splice(nums.length - 1, 1);
        heapq._heapify(nums, 0);
        return res;
    }

    private static _swapWithParent(nums: Val[], index: number) {
        if (index === 0) return;
        const parentIndex = Math.trunc((index - 1) / 2);
        if (nums[index][1] < nums[parentIndex][1]) {
            [nums[index], nums[parentIndex]] = [nums[parentIndex], nums[index]];
            heapq._swapWithParent(nums, parentIndex);
        }
    }

    private static _heapify(nums: Val[], index: number) {
        const leftChildIndex = index * 2 + 1;
        const rightChildIndex = index * 2 + 2;

        let minValueIndex = index;
        if (leftChildIndex < nums.length && nums[leftChildIndex][1] < nums[minValueIndex][1]) {
            minValueIndex = leftChildIndex;
        }
        if (rightChildIndex < nums.length && nums[rightChildIndex][1] < nums[minValueIndex][1]) {
            minValueIndex = rightChildIndex;
        }

        if (minValueIndex !== index) {
            [nums[index], nums[minValueIndex]] = [nums[minValueIndex], nums[index]];
            heapq._heapify(nums, minValueIndex);
        }
    }
}

function networkDelayTime(times: number[][], n: number, k: number): number {
    const aj = Array.from({ length: n }, _ => ([] as number[][]));
    for (const time of times) {
        const [u, v, w] = time;
        aj[u - 1].push([v - 1, w]);
    }

    const h = [[k - 1, 0] as Val];
    heapq.heapify(h);

    const visited = new Set<number>();
    let maxTime = 0;

    while (true) {
        // pop the node with minimum time
        const val = heapq.heappop(h);
        if (val === undefined) break;

        const [curNode, curTime] = val;

        // seen before, continue
        if (visited.has(curNode)) continue;
        visited.add(curNode);

        // this is used to calculate max time for this problem
        // not necessary for dijkstra
        maxTime = Math.max(maxTime, curTime);

        // push all neighbors into heap with new time
        for (const [nextNode, travelTime] of aj[curNode]) {
            heapq.heappush(h, [nextNode, curTime + travelTime])
        }
    }

    return visited.size < n ? -1 : maxTime;
};