Network Delay Time

mediumAdvanced Graphs (Dijkstra / MST)79 stepsJava · Python · C++

A signal starts at node k; how long until every node receives it? That's the largest shortest-path distance from k. Dijkstra's algorithm pops the closest unsettled node from a min-heap and relaxes its outgoing edges.

▶ Watch the animated trace

Traced input: times = [[2,1,1],[2,3,1],[3,4,1],[1,4,4]], n = 4, k = 2 → 2. Original problem: neetcode.io/problems/network-delay-time

Complexity

BestO(E log V)

AverageO(E log V)

WorstO(E log V)

SpaceO(V + E)

Each edge can push one heap entry.

Key idea

Weights are non-negative, so the closest unsettled node's distance is final.
Skip stale heap entries whose distance is larger than the recorded best.
Answer = max distance; if any node is unreachable, -1.

Common mistakes

Using BFS ignores the weights.
Forgetting to skip stale entries makes it slower (still correct).
Nodes are 1-indexed.

Solution

Java

int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] t : times) adj.get(t[0]).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) -> Integer.compare(a[1], b[1]));
    pq.offer(new int[]{k, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[0], d = top[1];
        if (d > dist[u]) continue;
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= n; i++) max = Math.max(max, dist[i]);
    return max == Integer.MAX_VALUE ? -1 : max;
}

Python

def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
    adj = defaultdict(list)
    for u, v, w in times: adj[u].append((v, w))
    dist = {k: 0}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")): continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return max(dist.values()) if len(dist) == n else -1

C++

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int, int>>> adj(n + 1);
    for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
    vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;
    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();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    int mx = *max_element(dist.begin() + 1, dist.end());
    return mx == INT_MAX ? -1 : mx;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Unreachable node Edges are directed: 2 can't reach 1.	`times = [[1,2,1]], n = 2, k = 2`	`-1`
Single node The signal is already everywhere.	`times = [], n = 1, k = 1`	`0`
Longer path is faster 1 → 3 → 2 costs 2, beating the direct edge of 10.	`times = [[1,2,10],[1,3,1],[3,2,1]], n = 3, k = 1`	`2`