Skip to main content
CodePeetCodePeet
CodePeet 150

Network Delay Time

MEDIUMProblemSolveExternal Links

Description

You are given a directed weighted network of n nodes, numbered from 1 to n. You are also given a list called times, where each entry times[i] = [uᵢ, vᵢ, wᵢ] represents a directed edge from node uᵢ to node vᵢ with a travel time of wᵢ.

A signal is sent from a designated starting node k. The signal propagates along directed edges, taking the specified travel time to traverse each edge. When the signal arrives at a node, it immediately continues forward along all outgoing edges from that node.

Return the minimum total time required for every node in the network to receive the signal. If some nodes are unreachable from k (meaning no directed path exists from k to that node), return -1.

In essence, you need to find the shortest path from node k to every other node and report the maximum among those shortest distances, since the last node to be reached determines when the entire network has been notified.

Directed weighted graph with 4 nodes showing edges from node 2 to nodes 1 and 3 (weight 1 each) and from node 3 to node 4 (weight 1). Signal starts at node 2.
Directed weighted graph with 4 nodes showing edges from node 2 to nodes 1 and 3 (weight 1 each) and from node 3 to node 4 (weight 1). Signal starts at node 2.

Examples

Example 1

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

Output: 2

Explanation: The signal starts at node 2 at time 0. It travels along edge 2→1 (weight 1) reaching node 1 at time 1, and along edge 2→3 (weight 1) reaching node 3 at time 1. From node 3, the signal continues along edge 3→4 (weight 1), reaching node 4 at time 1 + 1 = 2. All four nodes have received the signal, and the last one (node 4) receives it at time 2.

Example 2

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

Output: 1

Explanation: Node 1 is the source, so it has the signal at time 0. There is one edge from node 1 to node 2 with weight 1, so node 2 receives the signal at time 1. Both nodes are reached and the maximum delay is 1.

Example 3

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

Output: -1

Explanation: Node 2 is the source. The only edge goes from node 1 to node 2, so there is no way for the signal to reach node 1 from node 2. Since node 1 is unreachable, we return -1.

Constraints

  • 1 ≤ k ≤ n ≤ 100
  • 1 ≤ times.length ≤ 6000
  • times[i].length == 3
  • 1 ≤ uᵢ, vᵢ ≤ n
  • uᵢ ≠ vᵢ
  • 0 ≤ wᵢ ≤ 100
  • All the pairs (uᵢ, vᵢ) are unique (no multiple edges between the same pair of nodes)

Editorial

Brute Force - Bellman-Ford Algorithm

Intuition

The problem asks for the shortest time to reach every node from a source. This is fundamentally a single-source shortest path problem on a directed weighted graph.

The most straightforward way to find shortest paths is through a technique called edge relaxation. The idea is simple: if you know the shortest distance to node A, and there is an edge from A to B with weight w, then you can potentially reach B in dist[A] + w time. If this is shorter than the current known distance to B, you update it.

The Bellman-Ford algorithm applies this idea exhaustively. It loops through all edges up to V - 1 times (where V is the number of nodes). Why V - 1? Because the longest possible shortest path in a graph with V nodes can contain at most V - 1 edges. After V - 1 rounds of relaxing every edge, we are guaranteed to have found the shortest distance to every reachable node.

Think of it like a rumor spreading through a group of people connected by phone calls. In the first round, everyone who can be reached directly from the source hears the rumor. In the second round, people who are two hops away hear it. After V - 1 rounds, even the most distant person (up to V - 1 hops away) has been reached.

Once we have all shortest distances, the answer is the maximum distance among all nodes — the time when the last node is finally reached. If any node still has an infinite distance, it is unreachable, and we return -1.

Step-by-Step Explanation

Let's trace through Example 1: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2.

Edges: (2→1, w=1), (2→3, w=1), (3→4, w=1). Source node is 2.

Step 1: Initialize distances. Set dist[2] = 0 (source) and dist[1] = dist[3] = dist[4] = ∞ (unknown).

Step 2: Iteration 1 — Relax edge (2→1, w=1). dist[1] = min(∞, dist[2] + 1) = min(∞, 0 + 1) = 1. Updated! Node 1 is now reachable at time 1.

Step 3: Relax edge (2→3, w=1). dist[3] = min(∞, dist[2] + 1) = min(∞, 0 + 1) = 1. Updated! Node 3 is now reachable at time 1.

Step 4: Relax edge (3→4, w=1). dist[4] = min(∞, dist[3] + 1) = min(∞, 1 + 1) = 2. Updated! Node 4 is reachable at time 2 via the path 2→3→4.

Step 5: Iteration 2 — Relax edge (2→1, w=1). dist[1] = min(1, 0 + 1) = 1. No change — the current distance is already optimal.

Step 6: Relax edge (2→3, w=1). dist[3] = min(1, 0 + 1) = 1. No change.

Step 7: Relax edge (3→4, w=1). dist[4] = min(2, 1 + 1) = 2. No change. No distances were updated in this iteration, so we can stop early.

Step 8: All nodes are reachable. The distances are: node 1 = 1, node 2 = 0, node 3 = 1, node 4 = 2. The maximum distance is 2, which is our answer.

Bellman-Ford — Relaxing All Edges Repeatedly — Watch how the Bellman-Ford algorithm repeatedly relaxes every edge in the graph, progressively discovering shorter paths until no more improvements are possible.

Algorithm

  1. Initialize a distance array dist of size n + 1 with all values set to infinity, except dist[k] = 0 (the source node).
  2. Repeat the following up to V - 1 times (where V = n):
    • For each edge (u, v, w) in the edges list:
      • If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
    • If no distance was updated during this iteration, break early (all shortest paths have been found).
  3. Find the maximum value in the distance array (excluding index 0 if using 1-indexed nodes).
  4. If the maximum is infinity, return -1 (some node is unreachable). Otherwise, return the maximum.

Code

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // Initialize distances to infinity
        vector<int> dist(n + 1, INT_MAX);
        dist[k] = 0;
        
        // Relax all edges up to (n - 1) times
        for (int i = 0; i < n - 1; i++) {
            bool updated = false;
            for (auto& edge : times) {
                int u = edge[0], v = edge[1], w = edge[2];
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            // Early termination if no updates occurred
            if (!updated) break;
        }
        
        // Find the maximum distance among all nodes
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) return -1;
            maxDist = max(maxDist, dist[i]);
        }
        return maxDist;
    }
};
class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Initialize distances to infinity
        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        
        # Relax all edges up to (n - 1) times
        for i in range(n - 1):
            updated = False
            for u, v, w in times:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    updated = True
            # Early termination if no updates occurred
            if not updated:
                break
        
        # Find the maximum distance among all nodes
        max_dist = max(dist[1:])
        return -1 if max_dist == float('inf') else max_dist
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Initialize distances to infinity
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        
        // Relax all edges up to (n - 1) times
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (int[] edge : times) {
                int u = edge[0], v = edge[1], w = edge[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            // Early termination if no updates occurred
            if (!updated) break;
        }
        
        // Find the maximum distance among all nodes
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxDist = Math.max(maxDist, dist[i]);
        }
        return maxDist;
    }
}

Complexity Analysis

Time Complexity: O(V × E)

The outer loop runs up to V - 1 times, where V is the number of nodes. In each iteration, we examine all E edges to check for relaxation. This gives O(V × E) in the worst case. With V up to 100 and E up to 6000, this means up to 600,000 operations — well within time limits, but not the most efficient approach.

Space Complexity: O(V)

We use a single distance array of size V + 1. The input edge list is provided and not duplicated, so the additional space is linear in the number of nodes.

Why This Approach Is Not Efficient

Bellman-Ford is correct but does a lot of redundant work. In each iteration, it relaxes every single edge in the graph — even edges that cannot possibly lead to improvements because their source nodes haven't been updated since the last iteration.

Consider a graph with 100 nodes and 6000 edges. Bellman-Ford performs up to 99 × 6000 = 594,000 edge relaxation attempts. Most of these are wasted because the vast majority of edges connect nodes whose distances are already finalized.

The core inefficiency is that Bellman-Ford does not prioritize which nodes to process. It blindly iterates over everything. A smarter approach would process nodes in order of their shortest distance — the node closest to the source is finalized first, then the next closest, and so on. This way, each node is processed exactly once, and we only relax edges from nodes whose distances are already optimal.

This greedy insight is the foundation of Dijkstra's algorithm, which uses a priority queue (min-heap) to always pick the nearest unprocessed node and avoids the redundant relaxation that makes Bellman-Ford slower.

Optimal Approach - Dijkstra's Algorithm with Min-Heap

Intuition

Dijkstra's algorithm is a greedy shortest-path algorithm. Instead of blindly relaxing all edges repeatedly, it makes a clever observation: the unvisited node with the smallest current distance must already have its shortest path finalized.

Why is this true? Because all edge weights are non-negative. If node X currently has the smallest distance among all unprocessed nodes, no future relaxation can reduce its distance — any alternative path would go through some other unprocessed node first, which already has a larger distance, and adding a non-negative edge weight would only make it bigger.

Think of it like water flowing from a fountain (the source node). Water always reaches the nearest point first, then continues flowing outward. You never need to re-check a point that water has already reached, because water always finds the shortest path first.

The algorithm maintains a min-heap (priority queue) that stores (distance, node) pairs. At each step, we pop the pair with the smallest distance. If the node has already been processed, we skip it. Otherwise, we mark it as processed and relax all its outgoing edges, pushing any improvements back onto the heap.

Using a min-heap makes finding the minimum-distance node an O(log V) operation instead of O(V), which significantly speeds up the algorithm for sparse graphs.

Step-by-Step Explanation

Let's trace through Example 1: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2.

Adjacency list: 2 → [(1, 1), (3, 1)], 3 → [(4, 1)]. Source node is 2.

Step 1: Initialize distances: dist = {1: ∞, 2: 0, 3: ∞, 4: ∞}. Push (0, 2) onto the min-heap. The heap contains: [(0, 2)].

Step 2: Pop (0, 2) from heap — node 2 has the smallest distance (0). Mark node 2 as processed. Now examine its outgoing edges.

Step 3: Relax edge 2→1 (weight 1). dist[1] = min(∞, 0 + 1) = 1. Improved! Push (1, 1) onto heap. Heap: [(1, 1), (1, 3)].

Step 4: Relax edge 2→3 (weight 1). dist[3] = min(∞, 0 + 1) = 1. Improved! Push (1, 3) onto heap. Heap: [(1, 1), (1, 3)].

Step 5: Pop (1, 1) from heap — node 1 has distance 1. Mark node 1 as processed. Node 1 has no outgoing edges, so nothing to relax.

Step 6: Pop (1, 3) from heap — node 3 has distance 1. Mark node 3 as processed. Examine its outgoing edges.

Step 7: Relax edge 3→4 (weight 1). dist[4] = min(∞, 1 + 1) = 2. Improved! Push (2, 4) onto heap. Heap: [(2, 4)].

Step 8: Pop (2, 4) from heap — node 4 has distance 2. Mark node 4 as processed. Node 4 has no outgoing edges.

Step 9: Heap is empty. All 4 nodes are processed. Distances: node 1 = 1, node 2 = 0, node 3 = 1, node 4 = 2. Maximum = 2. Return 2.

Dijkstra's Algorithm — Greedy Shortest Path with Min-Heap — Watch how Dijkstra's algorithm always processes the nearest unvisited node, guaranteeing shortest paths are found efficiently without redundant work.

Algorithm

  1. Build an adjacency list from the input edges: for each edge (u, v, w), add (v, w) to the neighbors list of u.
  2. Initialize a distance array/dictionary with all values as infinity, except dist[k] = 0.
  3. Push (0, k) onto a min-heap.
  4. While the heap is not empty:
    • Pop (d, u) with the smallest distance.
    • If node u has already been processed, skip it.
    • Mark u as processed.
    • For each neighbor (v, w) of u:
      • If dist[u] + w < dist[v], update dist[v] = dist[u] + w and push (dist[v], v) onto the heap.
  5. Check if all nodes have been processed (distances are finite).
  6. If any node has infinite distance, return -1. Otherwise, return the maximum distance.

Code

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // Build adjacency list
        vector<vector<pair<int, int>>> graph(n + 1);
        for (auto& edge : times) {
            graph[edge[0]].push_back({edge[1], edge[2]});
        }
        
        // Distance array initialized to infinity
        vector<int> dist(n + 1, INT_MAX);
        dist[k] = 0;
        
        // Min-heap: (distance, node)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, k});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            // Skip if we've already found a better path
            if (d > dist[u]) continue;
            
            // Relax all outgoing edges
            for (auto& [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        // Find maximum distance
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) return -1;
            maxDist = max(maxDist, dist[i]);
        }
        return maxDist;
    }
};
import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Build adjacency list
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # Distance dictionary
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0
        
        # Min-heap: (distance, node)
        heap = [(0, k)]
        processed = set()
        
        while heap:
            d, u = heapq.heappop(heap)
            
            # Skip if already processed
            if u in processed:
                continue
            processed.add(u)
            
            # Relax all outgoing edges
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(heap, (dist[v], v))
        
        # Find maximum distance
        max_dist = max(dist.values())
        return -1 if max_dist == float('inf') else max_dist
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Build adjacency list
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : times) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        // Distance array initialized to infinity
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        
        // Min-heap: (distance, node)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});
        
        boolean[] processed = new boolean[n + 1];
        
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];
            
            // Skip if already processed
            if (processed[u]) continue;
            processed[u] = true;
            
            // Relax all outgoing edges
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        
        // Find maximum distance
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxDist = Math.max(maxDist, dist[i]);
        }
        return maxDist;
    }
}

Complexity Analysis

Time Complexity: O((V + E) × log V)

Building the adjacency list takes O(E). The main Dijkstra loop processes each node at most once, and for each node, we relax all its outgoing edges. Each heap operation (push/pop) costs O(log V). In the worst case, we push up to E entries onto the heap, so the total heap operations are O(E log V). Combined with the adjacency list construction, the total time is O(E log V). With V up to 100 and E up to 6000, this is approximately 6000 × 7 ≈ 42,000 operations — significantly faster than Bellman-Ford's 600,000.

Space Complexity: O(V + E)

The adjacency list stores all edges: O(E). The distance array and processed set each use O(V). The priority queue can hold at most O(E) entries in the worst case. Total space: O(V + E).