Network Delay Time

Leetcode Problem 743: Network Delay Time

Problem Summary

You are given a network of n nodes labeled from 1 to n and a list of directed weighted edges representing travel times. A signal is sent from a given node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1. The network can have up to 100 nodes and up to 6,000 edges, with edge weights ranging from 0 to 100. All source-target pairs are unique.

Techniques

Depth-First Search
Breadth-First Search
Graph Theory
Heap (Priority Queue)
Shortest Path

Solution

import { Heap } from "../heap";

type Edge = { node: number; cost: number };
type HeapNode = { node: number; cost: number };

function dijkstra(n: number, graph: Edge[][], start: number): number[] {
    const dist: number[] = Array(n).fill(Infinity);
    dist[start] = 0;

    const minCostHeap = new Heap<HeapNode>((a, b) => a.cost - b.cost);
    minCostHeap.insert({ node: start, cost: 0 });

    while (minCostHeap.size() > 0) {
        const current = minCostHeap.extract()!;
        const { node, cost } = current;

        if (cost > dist[node]) { 
            continue;
        }

        for (const { node: next, cost: weight } of graph[node]) {
            const newCost = cost + weight;

            if (newCost < dist[next]) {
                dist[next] = newCost;
                minCostHeap.insert({ node: next, cost: newCost });
            }
        }
    }

    return dist;
}

function createGraph(times: number[][], n: number) { 
    const graph: Edge[][] =  Array.from({ length: n }, () => []);

    for (const [u, v, w] of times) {
        graph[u - 1].push({ node: v - 1, cost: w }); // -1, nodes are labelled from 1 to n
    }

    return graph;
}

function networkDelayTime(times: number[][], n: number, k: number): number {
    const graph: Edge[][] = createGraph(times, n);
    const distances = dijkstra(n, graph, k - 1); // -1, nodes are labelled from 1 to n
    const maxDist = Math.max(...distances);

    return maxDist === Infinity ? -1 : maxDist;
};

console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)); // 2
console.log(networkDelayTime([[1,2,1]], 2, 1));