Network Delay Time medium

Problem Statement

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] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node k. Your task is to find the minimum time it takes for all nodes to receive the signal. If it's impossible, return -1.

Example 1

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

Output: 2

Explanation: The graph looks like this:

2 --> 1 (1)
2 --> 3 (1)
3 --> 4 (1)

The signal starts at node 2. It takes 1 unit of time to reach node 1 and node 3. Then it takes 1 unit of time to reach node 4 from node 3. Therefore, it takes 2 units of time to reach node 4, which is the last node to receive the signal.

Example 2

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

Output: 3

Steps

1. Build Adjacency List: Create an adjacency list to represent the graph. This allows for efficient traversal.
2. Dijkstra's Algorithm: Use Dijkstra's algorithm to find the shortest paths from the source node k to all other nodes. Dijkstra's algorithm is well-suited for finding shortest paths in graphs with non-negative edge weights.
3. Distance Array: Maintain a distance array (dist) to store the shortest distance from node k to each node. Initialize all distances to infinity except for the starting node k (distance 0).
4. Min-Heap (Priority Queue): Use a min-heap (priority queue) to efficiently select the node with the minimum distance. This ensures that we explore nodes in the order of their shortest distances.
5. Relaxation: Iteratively relax edges. For each node, check if a shorter path to its neighbors can be found by going through the current node. If so, update the distances in dist and the min-heap.
6. Maximum Distance: After Dijkstra's algorithm finishes, the maximum distance in the dist array represents the minimum time it takes for all nodes to receive the signal. If any node remains at infinity, it means it's unreachable, and we return -1.

Explanation

Dijkstra's Algorithm systematically explores the graph, prioritizing nodes closer to the source. The min-heap ensures that we always choose the node with the smallest distance, preventing us from exploring less efficient paths first. The relaxation step is crucial for finding shorter paths.

Code

import { MinPriorityQueue } from "@datastructures-js/priority-queue";

function networkDelayTime(times: number[][], n: number, k: number): number {
    // Build adjacency list
    const graph: { [key: number]: { node: number; weight: number }[] } = {};
    for (const [u, v, w] of times) {
        graph[u] = graph[u] || [];
        graph[u].push({ node: v, weight: w });
    }

    // Initialize distances
    const dist: number[] = Array(n + 1).fill(Infinity);
    dist[k] = 0;

    // Dijkstra's algorithm using min-heap
    const pq = new MinPriorityQueue({ priority: (x: { node: number; dist: number }) => x.dist });
    pq.enqueue({ node: k, dist: 0 });

    while (!pq.isEmpty()) {
        const { element, priority } = pq.dequeue();
        const u = element.node;
        const d = priority;

        if (d > dist[u]) continue; // Optimization: Skip if distance is already better

        if (graph[u]) {
            for (const { node: v, weight: w } of graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.enqueue({ node: v, dist: dist[v] });
                }
            }
        }
    }

    // Find maximum distance
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1; // Unreachable node
        maxDist = Math.max(maxDist, dist[i]);
    }

    return maxDist;
}

Remember to install @datastructures-js/priority-queue:

npm install @datastructures-js/priority-queue

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices (nodes). This is due to the use of Dijkstra's algorithm with a min-heap.
• Space Complexity: O(V + E), primarily due to the adjacency list and the distance array. The min-heap's space usage is also proportional to the number of vertices in the worst case.