Network Delay Time
Problem Statement
You are given a directed weighted graph with n nodes labelled 1..n. Each entry times[i] = [u, v, w] means a signal can travel from node u to node v in w time.
A signal is sent from source node k. Return the minimum time needed for all nodes to receive the signal. If at least one node is unreachable, return -1.
Input
An edge list times, the number of nodes n, and the source node k.
Output
An integer: the maximum shortest-path distance from k to any node, or -1 if some node cannot be reached.
Constraints
- •
1 <= k <= n <= 100 - •
1 <= times.length <= 6000 - •
times[i].length == 3 - •
1 <= u, v <= n - •
u != v - •
0 <= w <= 100 - •
All edges are directed.
Examples
Example 1
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
2Example 2
times = [[1,2,1]], n = 2, k = 1
1Example 3
times = [[1,2,1]], n = 2, k = 2
-1Learning Objectives
- Translate network propagation into single-source shortest paths on a directed weighted graph.
- Use Dijkstra with a min-heap when edge weights are non-negative.
- Understand Bellman-Ford as a relaxation-based alternative for single-source shortest paths.
- Compute the final answer as the maximum finite shortest distance, not the distance to one target.
Intuition
The signal reaches each node as soon as the fastest route from k to that node finishes. So the problem is not asking for one path; it asks for all shortest distances from one source. Once those distances are known, the network delay is simply the slowest arrival time among them.
For non-negative edge weights, Dijkstra is the fastest standard fit. It repeatedly settles the currently closest unsettled node. That is safe because any alternative route to that node would have to add a non-negative edge after an already equal-or-larger distance.
Bellman-Ford thinks differently: instead of always expanding the closest node, it repeatedly relaxes every edge. After one full pass it knows best paths using at most one edge; after two passes, at most two edges; after n - 1 passes, every simple shortest path is covered. It is slower, but the relaxation idea is foundational and handles the more general single-source shortest-path template.
The last step is easy to miss: return the maximum shortest distance. If any distance stayed infinite, the signal never reaches every node.
Common mistakes
- ×Treating the graph as undirected even though every edge is directed.
- ×Returning the distance to the last processed node instead of max over all nodes.
- ×Forgetting nodes are labelled 1..n and accidentally sizing arrays for 0..n - 1 only.
- ×Marking a node permanently visited before its minimum heap entry is popped; stale heap entries should be skipped by comparing with dist.
- ×Using plain BFS on weighted edges. BFS only works when every edge has equal cost.
Algorithm Explanation
Dijkstra: build an adjacency list, initialise dist[k] = 0, and use a min-heap ordered by current known distance. Pop the closest state; if it is stale, skip it. Otherwise relax each outgoing edge and push improved distances. After the heap drains, return the max dist or -1 if any node is still unreachable.
Bellman-Ford: initialise distances the same way, then relax every directed edge up to n - 1 times. A pass that makes no changes can stop early. Finally compute the same max-or-unreachable answer.
Dijkstra is preferred here because weights are non-negative and the graph may have many edges. Bellman-Ford is valuable when you want the simplest relaxation skeleton or when a variant may introduce negative edges.
Solutions
Solution 1: Dijkstra with a min-heap
Use this as the interview default for directed graphs with non-negative weights. It is faster than Bellman-Ford on sparse and medium-dense graphs and naturally returns all shortest distances from the source.
Store outgoing edges in an adjacency list. The priority queue always gives the currently smallest known arrival time. Relaxing an edge means asking whether reaching the neighbour through the current node improves its best known arrival time.
Step-by-step
- Build graph[u] as pairs of neighbour and travel time.
- Fill dist with infinity and set dist[k] = 0.
- Push source into a priority queue ordered by time.
- Pop the smallest time. If it is larger than dist[node], it is stale and can be ignored.
- Relax all outgoing edges.
- Scan dist[1..n]; if any node is infinity return -1, otherwise return the maximum distance.
O((n + E) log n)
O(n + E)
E is times.length. The adjacency list stores E directed edges and the heap stores candidate distances.
Java implementation
Solution 2: Bellman-Ford edge relaxation
Use this when you want a compact relaxation template, when the graph representation is already an edge list, or in variants where negative weights might appear. It is slower but very robust conceptually.
A shortest simple path in a graph with n nodes uses at most n - 1 edges. Repeatedly relaxing every edge propagates best distances one edge farther per round until no improvement remains.
Step-by-step
- Set all distances to infinity except dist[k] = 0.
- For up to n - 1 rounds, scan every edge [u, v, w].
- If u is reachable and dist[u] + w improves dist[v], update dist[v].
- Stop early if a full round changes nothing.
- Return max distance, or -1 if any node is unreachable.
O(n · E)
O(n)
At most n - 1 full edge-relaxation passes are needed.
Java implementation
Dry Run
Sample input
Dijkstra trace for times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2.
| Step | Heap pop | Relaxed edges | dist after step | Heap after step |
|---|---|---|---|---|
| 1 | (2,0) | 2 → 1 gives 1; 2 → 3 gives 1 | {1:1, 2:0, 3:1, 4:∞} | [(1,1), (3,1)] |
| 2 | (1,1) | node 1 has no outgoing edges | {1:1, 2:0, 3:1, 4:∞} | [(3,1)] |
| 3 | (3,1) | 3 → 4 gives 2 | {1:1, 2:0, 3:1, 4:2} | [(4,2)] |
| 4 | (4,2) | node 4 has no outgoing edges | {1:1, 2:0, 3:1, 4:2} | [] |
| 5 | scan distances | all nodes reachable | max = 2 | return 2 |
The shortest arrival times are 0 for source 2, 1 for nodes 1 and 3, and 2 for node 4. The network is complete only when the slowest reachable node receives the signal, so the answer is 2.
Interview Tips
Lead with single-source shortest paths, then choose Dijkstra because weights are non-negative. Be explicit that the final answer is not a particular target distance; it is the maximum of all shortest distances. If asked for alternatives, give Bellman-Ford and explain the n - 1 relaxation rounds. If the interviewer mentions negative edges, Dijkstra is no longer safe; that is the cue for Bellman-Ford.
Likely follow-ups
- Return the actual path tree that delivers the signal fastest to every node.
- What changes if edge weights can be negative? Use Bellman-Ford and detect negative cycles if relevant.
- What if the graph is undirected? Add both directions to the adjacency list.
- What if many sources send the signal at time 0? Seed Dijkstra with all sources at distance 0.
Similar Problems
Key Takeaways
- Network delay is max shortest distance from the source.
- Dijkstra is correct for non-negative weighted edges because the smallest unsettled distance cannot later improve.
- Bellman-Ford relaxes all edges repeatedly and is the general edge-list single-source template.
- Directed edges must not be mirrored unless the problem says the graph is undirected.