Course4all
Join us on telegram
Home/dsa/Graphs/Network Delay Time

Network Delay Time

Master this topic with zero to advance depth.

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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.

Visual Representation

Nodes: 4, Times: [[2,1,1],[2,3,1],[3,4,1]], K: 2 (1) <--1-- (2) --1--> (3) --1--> (4) Signal at 2 reaches 1 and 3 at T=1. Signal reaches 4 at T=2. Result: 2
Medium

Examples

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

Signal reaches all nodes in 2 units of time.

Approach 1

Level I: Brute Force (Bellman-Ford)

Intuition

Bellman-Ford is a simpler shortest path algorithm that works by repeatedly relaxing all edges. After N−1N-1 iterations, all shortest paths are guaranteed to be found.

Thought Process

  1. Initialize dist array with infinity, dist[k] = 0.
  2. For N−1N-1 iterations:
    • For each edge (u,v,w)(u, v, w) in times:
      • If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
  3. After N−1N-1 iterations, check max(dist). If any node is still at infinity, return -1.

Why it's Level I

It is computationally slower than Dijkstra but much simpler to implement correctly as it doesn't require a priority queue.

⏱ O(V * E) - Where V is nodes and E is edges.💾 O(V) - To store distances.

Detailed Dry Run

n=4, k=2, edges=[[2,1,1],[2,3,1],[3,4,1]]

  1. Init: dist=[inf, 0, inf, inf] (using 1st index for node 1)
  2. Iter 1:
    • edge (2,1,1): dist[1]=1
    • edge (2,3,1): dist[3]=1
    • edge (3,4,1): dist[4]=1+1=2
  3. Iter 2 & 3: No changes. Max dist = 2
java
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int[] t : times) {
                int u = t[0], v = t[1], w = t[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        int maxT = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxT = Math.max(maxT, dist[i]);
        }
        return maxT;
    }
}
Approach 2

Level III: Optimal (Dijkstra's Algorithm)

Intuition

This is a single-source shortest path problem on a weighted graph with non-negative weights. Dijkstra's algorithm uses a priority queue to always expand the node with the smallest known distance.

Thought Process

  1. Build an adjacency list: u -> (v, w).
  2. Initialize a dist array with infinity, dist[k] = 0.
  3. Use a Min-Priority Queue to store (time, node) pairs.
  4. While the queue is not empty:
    • Pop (t, u). If t > dist[u], continue (stale entry).
    • For each neighbor (v, weight) of u:
      • If dist[u] + weight < dist[v]:
        • Update dist[v] = dist[u] + weight and push to queue.
  5. The answer is max(dist). If any node is unreachable (infinity), return -1.

Pattern: Shortest Path (Dijkstra)

⏱ O(E log V) where E is edges and V is nodes.💾 O(V + E) for the adjacency list.

Detailed Dry Run

n=4, k=2, edges=[[2,1,1],[2,3,1],[3,4,1]]

PQ (t,u)dist[]Action
(0,2)[inf, 0, inf, inf]Init
(1,1), (1,3)[1, 0, 1, inf]Pop 2, relax 1 & 3
(1,3)[1, 0, 1, inf]Pop 1
(2,4)[1, 0, 1, 2]Pop 3, relax 4
Max(dist) = 2
java
import java.util.*;

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] t : times) {
            adj.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0], u = curr[1];
            if (t > dist[u]) continue;
            if (adj.containsKey(u)) {
                for (int[] next : adj.get(u)) {
                    int v = next[0], w = next[1];
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxTime = Math.max(maxTime, dist[i]);
        }
        return maxTime;
    }
}
← Previous QuestionMinimum Height Trees
Next Question →Cheapest Flights Within K Stops