Network Delay Time

Problem in Plain English

A signal leaves node k and fans out along every directed link at once, each link adding its own travel seconds. Return when the last of the n nodes hears the signal, or -1 when some node is unreachable.

Problem Statement

You are given a network of n nodes labelled 1 to n and a list times where times[i] = [u, v, w] is a directed edge: a signal needs w seconds to travel from u to v.

Send a signal from node k. It fans out along every link simultaneously, so each node hears it via its fastest route. Return the time when the last node receives the signal, or -1 if some node can never receive it.

Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u, v <= n
u != v
0 <= w <= 100
No (u, v) pair appears twice.

Examples

Example 1

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

Nodes 1 and 3 hear the signal at time 1, and node 4 hears it through node 3 at time 2.

Example 2

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

The single link carries the signal to node 2 in one second.

Example 3

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

The only link is 1 -> 2. Starting at node 2 cannot traverse it backwards, so node 1 never hears the signal even though the undirected network would be connected.

Example 4

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

The direct arrival at node 2 would be 9, but 1 -> 3 -> 2 takes only 1 because the second link costs zero. Node 4 then arrives at 3. The fastest arrivals are [0, 1, 1, 3]; a heap may still contain the obsolete (9,2) route, which must be skipped.

Intuition

Each node receives the signal along its fastest directed route from k; these shortest arrival times happen in parallel, so the answer is their maximum, not their sum. In Example 1, arrivals for nodes 1 through 4 are [1, 0, 1, 2], making the delay 2. Relaxing an edge means improving its destination arrival using a known arrival at its source plus the edge weight. Bellman-Ford repeats all such checks; Dijkstra uses non-negative weights to settle the smallest pending arrival first. A node with no route from k makes the entire answer -1.

Approaches

Bellman Ford Relax All

Solution Details

Reveal Bellman Ford Relax All: intuition, complexity, and code

Intuition

A shortest route can be chosen without repeated nodes because deleting a non-negative cycle never increases its cost. Such a route uses at most $n - 1$ links. Scan every edge repeatedly to propagate known arrivals one link farther per round; favorable edge ordering can propagate several links in one round, as in Example 1. Stop when a full round changes nothing, or after $n - 1$ rounds. This avoids needing a heap but spends work rescanning every edge.

Step-by-Step Logic

Start Example 1 with dist = [inf, inf, 0, inf, inf] for indices 0 to 4, with only source 2 at 0.
Round 1 scans all three links: 2 -> 1 sets dist[1] = 1, 2 -> 3 sets dist[3] = 1, and 3 -> 4 sets dist[4] = 2.
Round 2 scans all three links again: no distance improves, so stop early.
Every node 1 to 4 holds a finite distance, so none is unreachable.
Return the largest distance, max(1, 0, 1, 2) = 2.

Why It Works

Every finite distance is the cost of an actual route from k, so relaxation cannot invent an arrival earlier than the true shortest route. After round r, all shortest routes using at most r edges have been accounted for: the prefix using at most r - 1 edges was known before this round, and scanning its final edge supplies the complete route. In-place updates can only discover extra routes sooner. Non-negative cycles can be removed, so a shortest route needs at most n - 1 edges, proving the round limit. If a whole round makes no change, all edge inequalities already hold and subsequent rounds cannot change anything. Unreachable nodes remain infinite; otherwise taking the maximum gives the last first-arrival time.

Dry Run

Bellman Ford Relax All: variable states at each step
Round	Edge / candidate	Update	changed	dist[1..4]
start	source 2	dist[2] = 0	-	[inf, 0, inf, inf]
1	2 -> 1: 0 + 1 = 1	inf -> 1	true	[1, 0, inf, inf]
1	2 -> 3: 0 + 1 = 1	inf -> 1	true	[1, 0, 1, inf]
1	3 -> 4: 1 + 1 = 2	inf -> 2	true	[1, 0, 1, 2]
2	2 -> 1: candidate 1	equal, no update	false	[1, 0, 1, 2]
2	2 -> 3: candidate 1	equal, no update	false	[1, 0, 1, 2]
2	3 -> 4: candidate 2	equal, no update; stop	false	[1, 0, 1, 2]
finish	scan nodes 1, 2, 3, 4	all finite; max: 1 -> 1 -> 1 -> 2	-	return 2

Complexity Analysis

Time Complexity

O(n * E)

Space Complexity

O(n)

Let E be times.length. At most n - 1 rounds scan E edges, plus O(n) initialization and the final scan; for legal inputs E >= 1 and n >= 2, this is O(nE). Only the n + 1 distance array is needed; Python also allocates an O(n) slice for its final max, without changing the bound. The input is not copied or mutated. A shortest simple route costs at most 99 * 100 = 9900; the guard prevents adding to Java Integer.MAX_VALUE.

Code

Solution.java

1import java.util.Arrays;2
3class Solution {4    public int networkDelayTime(int[][] times, int n, int k) {5        int[] dist = new int[n + 1];6        Arrays.fill(dist, Integer.MAX_VALUE);7        dist[k] = 0;8        for (int i = 0; i < n - 1; i++) {9            boolean changed = false;10            for (int[] t : times) {11                int u = t[0];12                int v = t[1];13                int w = t[2];14                // Do not add to the infinity sentinel; each update is a real route.15                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {16                    dist[v] = dist[u] + w;17                    changed = true;18                }19            }20            // A fixed point satisfies every relaxation and needs no more rounds.21            if (!changed) {22                break;23            }24        }25        int max = 0;26        for (int i = 1; i <= n; i++) {27            if (dist[i] == Integer.MAX_VALUE) {28                return -1;29            }30            max = Math.max(max, dist[i]);31        }32        return max;33    }34}

Hints

Hint 1

The finishing time is the slowest of the fastest routes, since every link carries the signal in parallel.

Hint 2

Non-negative travel times mean the unsettled node with the smallest tentative time is already final.

Hint 3

A min-heap always hands over that closest unsettled node next, and unvisited nodes at the end mean -1.

Edge Cases

A disconnected graph where some node stays unvisited, which must return -1 rather than a partial maximum.
Zero-weight links and zero-weight cycles can give many nodes the same arrival time; settling each node once prevents repeated expansion.
An expensive direct edge may be beaten by several cheaper links; for [[1,2,9],[1,3,1],[3,2,0]], source 1 reaches node 2 at time 1.
A reverse-ordered chain can require all n - 1 Bellman-Ford rounds; early exit must follow a whole unchanged pass.
A defensive n = 1, times = [] call returns 0, though this is outside the published minimum edge-count constraint.

Common Mistakes and Interview Tips

Adding every arrival time together instead of taking the maximum, which forgets the links carry the signal in parallel.
Returning the maximum without checking that all n nodes were settled, which reports a time for unreachable graphs.
Replacing the heap with an unordered queue and settling on first dequeue fails when a route with more edges is cheaper.
Marking a node visited when pushing it locks in a tentative arrival; settle only when the minimum route is popped.
Scanning outgoing edges again for stale heap entries can inflate work; skip visited nodes immediately after popping.
Summing delays, treating links as undirected, or including unused index 0 in the maximum changes the answer.
Interview tip: explain why zero weights preserve the Dijkstra proof and why negative weights would invalidate settlement. State that this lazy heap can hold O(E) route entries, not only O(n).

Key Takeaway

Single-source arrival times on non-negative weights belong to Dijkstra: always expand the closest unsettled node and read the answer off the largest settled distance.