Network Delay Time

Difficulty: Medium Source: NeetCode

Problem

You are given a network of n nodes, labeled 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi 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 n nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

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

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

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• 0 <= wi <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dijkstra’s Algorithm — finding shortest paths in a weighted directed graph
• Adjacency List — representing a graph efficiently
• Heapq — Python’s min-heap module

1. Brute Force (Bellman-Ford)

Intuition

Bellman-Ford relaxes all edges up to n-1 times. After all relaxations, dist[v] holds the shortest path from k to every node v. If any node still has infinite distance, it’s unreachable. This is simpler to reason about than Dijkstra but slower.

Algorithm

1. Initialize dist[k] = 0 and dist[all others] = infinity.
2. Repeat n-1 times: for each edge (u, v, w), if dist[u] + w < dist[v], update dist[v].
3. If any dist[v] is still infinity, return -1.
4. Otherwise, return max(dist.values()).

Solution

def networkDelayTime_bf(times, n, k):
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[k] = 0

    for _ in range(n - 1):
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    max_dist = max(dist.values())
    return max_dist if max_dist < float('inf') else -1


print(networkDelayTime_bf([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))  # 2
print(networkDelayTime_bf([[1, 2, 1]], 2, 1))                          # 1
print(networkDelayTime_bf([[1, 2, 1]], 2, 2))                          # -1

Complexity

• Time: O(n * E) where E is the number of edges
• Space: O(n)

2. Dijkstra’s Algorithm

Intuition

Since all edge weights are non-negative, Dijkstra is the right tool here. We want the shortest path from source k to every other node. The answer is simply the maximum of all those shortest distances — because the signal must reach the last node to arrive. If any node is unreachable, we return -1.

Think of it like water flowing through pipes: the time for all nodes to receive the signal is determined by the slowest (furthest) one.

Algorithm

1. Build an adjacency list from the edge list.
2. Initialize dist = {k: 0} and push (0, k) into the min-heap.
3. While the heap is not empty:
   • Pop (time, node).
   • If time > dist[node], skip (stale).
   • For each neighbor (v, w), if dist[node] + w < dist.get(v, inf), update and push.
4. If len(dist) < n, return -1 (some nodes unreachable).
5. Return max(dist.values()).

Solution

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    dist = {}
    heap = [(0, k)]  # (time, node)

    while heap:
        time, node = heapq.heappop(heap)

        if node in dist:
            continue  # already found shortest path to this node
        dist[node] = time

        for v, w in graph[node]:
            if v not in dist:
                heapq.heappush(heap, (time + w, v))

    return max(dist.values()) if len(dist) == n else -1


print(networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))  # 2
print(networkDelayTime([[1, 2, 1]], 2, 1))                          # 1
print(networkDelayTime([[1, 2, 1]], 2, 2))                          # -1
print(networkDelayTime([[1, 2, 1], [2, 3, 2]], 3, 1))              # 3

Complexity

• Time: O(E log V) where E is edges and V is nodes
• Space: O(V + E) for the graph and heap

Common Pitfalls

Returning max distance without checking reachability. If a node is disconnected from k, it will never appear in dist. Always check len(dist) == n before returning.

Using 0-indexed nodes when the problem uses 1-indexed. This problem uses nodes labeled 1 to n. Be careful not to accidentally use 0-indexed arrays.

Confusing “time to reach all nodes” with “time to reach destination”. The answer is max(dist.values()), not just the distance to a single target — every node needs the signal.