Problem statement

A network has n nodes labelled 1..n. times[i] = [u, v, w] means a signal takes w time to travel from u to v (directed). A signal is sent from node k.

Return the time for all nodes to receive it, or -1 if some node never does.

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 = 2
Output: -1

Constraints

• 1 <= n <= 10
• 1 <= times.length <= 30
• 1 <= w <= 50

Hints for Network Delay Time

1. Hint 1

   Single-source shortest paths — Dijkstra from k.

2. Hint 2

   The answer is the maximum shortest distance; Infinity anywhere means -1.

How to solve Network Delay Time

"When has everyone received the signal?" is the moment the last node receives it — and each node receives it along its shortest path from k. So compute single-source shortest paths from k and take the maximum. If any node is unreachable, the signal never fully propagates and the answer is -1.

Approach

1. Set every distance to infinity except dist[k] = 0.
2. Relax repeatedly: for each edge u -> v with weight w, if dist[u] + w < dist[v], improve dist[v].
3. Repeat up to n - 1 rounds, stopping early if a full round changes nothing.
4. Scan all n nodes: if any is still infinite, return -1.
5. Otherwise return the largest distance.

Why it works

A shortest path in a graph with n nodes visits at most n - 1 edges, so n - 1 rounds of relaxing every edge is enough for the correct distance to propagate outward one hop per round — this is Bellman-Ford. All weights are positive, so no negative cycles can distort it, and Dijkstra with a min-heap computes the same distances faster. The maximum is right because the signal reaches every node in parallel, so total time is set by the slowest arrival.

Complexity

• Time — O(V · E) with Bellman-Ford, O(E log V) with Dijkstra
• Space — O(V)

Pitfalls

• Nodes are labelled 1..n, so size the distance array n + 1 and scan from 1.
• Guard against relaxing from an unreachable node — adding a weight to "infinity" and storing it produces bogus finite distances.
• The answer is the maximum of the shortest distances, not their sum.
• The edges are directed; do not add the reverse.

Reference solution

Python

from typing import List
import heapq
from collections import defaultdict

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 = {}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue
        dist[u] = d
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    if len(dist) != n:
        return -1
    return max(dist.values())

Java

public static int networkDelayTime(int[][] times, int n, int k) {
    final int INF = 1000000000;
    int[] dist = new int[n + 1];
    Arrays.fill(dist, INF);
    dist[k] = 0;
    for (int round = 0; round < n; round++) {
        boolean changed = false;
        for (int[] t : times) {
            if (dist[t[0]] != INF && dist[t[0]] + t[2] < dist[t[1]]) {
                dist[t[1]] = dist[t[0]] + t[2];
                changed = true;
            }
        }
        if (!changed) break;
    }
    int worst = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) return -1;
        if (dist[i] > worst) worst = dist[i];
    }
    return worst;
}

C++

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    const int INF = 1000000000;
    vector<int> dist(n + 1, INF);
    dist[k] = 0;
    for (int round = 0; round < n; round++) {
        bool changed = false;
        for (const auto& t : times) {
            if (dist[t[0]] != INF && dist[t[0]] + t[2] < dist[t[1]]) {
                dist[t[1]] = dist[t[0]] + t[2];
                changed = true;
            }
        }
        if (!changed) break;
    }
    int worst = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) return -1;
        if (dist[i] > worst) worst = dist[i];
    }
    return worst;
}

JavaScript

var networkDelayTime = function(times, n, k) {
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    const done = new Array(n + 1).fill(false);
    for (let iter = 0; iter < n; iter++) {
        let u = -1;
        for (let v = 1; v <= n; v++) {
            if (!done[v] && (u === -1 || dist[v] < dist[u])) u = v;
        }
        if (u === -1 || dist[u] === Infinity) break;
        done[u] = true;
        for (const t of times) {
            if (t[0] === u && dist[u] + t[2] < dist[t[1]]) dist[t[1]] = dist[u] + t[2];
        }
    }
    let best = 0;
    for (let v = 1; v <= n; v++) {
        if (dist[v] === Infinity) return -1;
        best = Math.max(best, dist[v]);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium