Network Delay Time
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of directed edges timesi = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from u to v. A signal starts at a given node k . Return the minimum time it takes for all n nodes to receive the signal, or -1 if it is impossible for all nodes to receive it. Run Dijkstra's algorithm from k, popping the cheapest not-yet-finalized node each round. The answer is the largest finalized distance across every node.
Constraints
- 1 ≤ k ≤ n ≤ 100
- 1 ≤ times.length ≤ 6000
- timesi.length == 3
- 1 ≤ ui, vi ≤ n
- ui != vi
- 0 ≤ wi ≤ 100
- All the pairs (ui, vi) are unique
Example
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22Explanation From node 2, node 1 and node 3 are reached at time 1, and node 4 is reached at time 2 (through node 3). The slowest node to hear the signal is 2 time units away.
In plain terms
- Directed edge
- A one-way connection — an edge (u, v, w) only lets a signal travel from u to v, not the other way.
Pop the cheapest unfinalized node, relax its neighbors
Start at node 2, distance 0. Every other node is unknown.
What happens in this step
dist[2] = 0 dist[1] = dist[3] = dist[4] = ∞ Every node starts unreachable except the source, node 2, which is 0 time units from itself.
Steps to visualize
- Set the distance of the source k to 0 and every other node to infinity.
- Repeatedly pop the unfinalized node with the smallest distance.
- Relax its outgoing edges: if going through this node beats a neighbor’s current distance, update it.
- Once every node is finalized, the largest distance is the answer — or -1 if any node is still infinity.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start at node 2, distance 0. Every other node is unknown.
What happens in this step
dist[2] = 0 dist[1] = dist[3] = dist[4] = ∞ Every node starts unreachable except the source, node 2, which is 0 time units from itself.
Solution
function networkDelayTime(times, n, k) {
const adj = new Map();
for (let i = 1; i <= n; i++) adj.set(i, []);
for (const [u, v, w] of times) {
adj.get(u).push([v, w]);
}
const dist = new Map();
for (let i = 1; i <= n; i++) dist.set(i, Infinity);
dist.set(k, 0);
const visited = new Set();
while (visited.size < n) {
let current = -1;
let best = Infinity;
for (let i = 1; i <= n; i++) {
if (!visited.has(i) && dist.get(i) < best) {
best = dist.get(i);
current = i;
}
}
if (current === -1) break;
visited.add(current); // finalized — never revisited
for (const [neighbor, weight] of adj.get(current)) {
const candidate = dist.get(current) + weight;
if (candidate < dist.get(neighbor)) {
dist.set(neighbor, candidate);
}
}
}
let maxDist = 0;
for (let i = 1; i <= n; i++) {
const d = dist.get(i);
if (d === Infinity) return -1;
maxDist = Math.max(maxDist, d);
}
return maxDist;
}- Time
- O(n^2 + E)
- Space
- O(n + E)
Test cases
| Input | Expected | Covers |
|---|---|---|
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 | 2 | example from the docstring |
times = [[1,2,1]], n = 2, k = 2 | -1 | a node cannot be reached at all |
times = [], n = 1, k = 1 | 0 | only the source node exists, no edges needed |
times = [[1,2,1]], n = 2, k = 1 | 1 | smallest non-trivial case, a single direct edge |
times = [[1,2,5],[1,2,1]], n = 2, k = 1 | 1 | two parallel edges between the same nodes, relaxation keeps the cheaper one |
times = [[1,2,10],[1,3,1],[3,2,1],[2,4,1],[3,4,10]], n = 4, k = 1 | 3 | an indirect route beats a direct edge after relaxation |
times = [[1,2,1],[1,3,1]], n = 3, k = 1 | 1 | every node is reached directly, both at the same distance |