You have a network of n nodes labelled 1 to n. You are given times, a list of directed travel times times[i] = [u, v, w] meaning a signal takes w time to travel from node u to node v.
A signal is sent from node k. Return the minimum time for all n nodes to receive the signal. If it is impossible for every node to receive it, return -1.
The time for all nodes to receive the signal is the latest of the shortest arrival times — the signal reaches each node along its fastest route, and you wait for the slowest of those.
Example
From node 2: node 1 arrives at t=1, node 3 at t=1, node 4 at t=2. The slowest is 2.
Constraints
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= u, v <= n
- u != v
- 0 <= w <= 100
- All pairs (u, v) are unique (no duplicate edges).
Intuition
A signal leaves node k and travels along weighted directed edges; we want the moment all nodes have received it — the largest shortest-arrival-time over every node, or -1 if one is unreachable. Since edges carry different costs, a plain BFS (which counts edges, not cost) gives the wrong answer; the textbook starting point is Bellman–Ford, relaxing every edge V − 1 times.
function networkDelayTime(times, n, k) {
const dist = new Array(n + 1).fill(Infinity);
dist[k] = 0;
// V-1 rounds; each round tries to shorten every edge.
for (let round = 0; round < n - 1; round++) {
for (const [u, v, w] of times) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w; // found a cheaper route to v
}
}
}
let slowest = 0;
for (let node = 1; node <= n; node++) {
if (dist[node] === Infinity) return -1;
slowest = Math.max(slowest, dist[node]);
}
return slowest;
}Bellman–Ford re-relaxes every edge in every round, even edges whose endpoints didn't change. Can we do better?
The key observation: with non-negative weights, once we settle the closest unsettled node its distance is final — no later, longer detour can improve it. That's Dijkstra: keep a frontier of (distance, node), always expand the smallest-distance node next, and relax its outgoing edges. Each node settles once; with a heap the cost is O(E log V). The answer is the max settled distance, or -1 if any node stays at Infinity.
A weighted graph has no faithful lane animation, so the static picture and a distance trace serve better than a misleading one. Example: times = [[2,1,1],[2,3,1],[3,4,1]], k = 2.
- Settle once, skip stale entries. A node can sit in the frontier under several distances; when you pop one whose distance already exceeds the recorded best, skip it — it's a superseded entry.
- Dijkstra needs non-negative weights. The settle-and-never-revisit guarantee breaks with a negative edge; that case wants Bellman–Ford instead. Here weights are
0..100, so Dijkstra is safe. - The stored solution uses a sort-based frontier rather than a binary heap — same algorithm, an extra log factor, plenty fast for
n ≤ 100. The(d > dist[u])guard is the stale-entry skip.
Optimization
Dijkstra's shortest paths
The signal reaches each node along its shortest weighted path from k, so the answer is the largest shortest-path distance over all nodes (or -1 if any node is unreachable). With non-negative weights, Dijkstra computes those distances.
Keep a dist array (all Infinity except dist[k] = 0) and a min-priority queue keyed by tentative distance, seeded with (0, k). Pop the closest unsettled node, and for each outgoing edge u -> v of weight w, relax dist[v] to dist[u] + w when that's an improvement, pushing the new (dist[v], v). A node is settled the first time it is popped (its distance can't improve after that).
When the queue drains, the answer is max(dist[1..n]) — unless some node is still Infinity, in which case return -1.
O(E log V) time with a binary heap and O(V + E) space. (This implementation uses a sort-based "pop the current minimum" queue, which keeps the code compact at the cost of an extra log factor — still ample for the constraints.)
function networkDelayTime(times, n, k) {
// adj[u] = list of [v, w] edges out of u (nodes are 1-indexed).
const adj = Array.from({ length: n + 1 }, () => []);
for (const [u, v, w] of times) adj[u].push([v, w]);
const dist = new Array(n + 1).fill(Infinity);
dist[k] = 0;
// Frontier of (distance, node); we always expand the smallest distance next.
const frontier = [[0, k]];
while (frontier.length > 0) {
// Pull out the node with the current minimum tentative distance.
frontier.sort((a, b) => a[0] - b[0]);
const [d, u] = frontier.shift();
if (d > dist[u]) continue; // a stale, already-improved entry
for (const [v, w] of adj[u]) {
// Relax the edge: a shorter route to v through u?
if (d + w < dist[v]) {
dist[v] = d + w;
frontier.push([dist[v], v]);
}
}
}
// The time for all nodes is the slowest shortest arrival; Infinity means unreachable.
let slowest = 0;
for (let node = 1; node <= n; node++) {
if (dist[node] === Infinity) return -1;
slowest = Math.max(slowest, dist[node]);
}
return slowest;
}Complexity analysis
Time complexity: O(E log V) with a binary heap (the stored sort-based frontier is a slower-by-a-log variant). Here's why:
- Each of the
Eedges is relaxed at most once, and each relaxation pushes onto the frontier. - A heap pop/push is
O(log V); the final max-distance scan isO(V).
So the dominant cost is the edge relaxations through the frontier — O(E log V).
Space complexity: O(V + E). Here's why:
- The adjacency lists hold all
Eedges; thedistarray isO(V). - The frontier holds at most
O(E)entries before stale ones are skipped.
So the extra space is O(V + E).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| times = [], n = 1, k = 1 | 0 | The source is the only node — zero time. |
| times = 127 | 7 | A single edge from the source — arrival time 7. |
| times = 127 | -1 | The only edge points away from the source — node 1 unreachable. |
| times = 129 131 321 | 2 | A two-hop route (1→3→2 = 2) beats the slow direct edge (1→2 = 9). |
| times = 123 132 145 | 5 | A star from the source — the slowest direct arrival (5) sets the answer. |
Try it yourself
Write your solution against the real judge before checking the reference.