Network Delay Time
Medium · Advanced Graphs · Graph · Shortest Path · Heap (Priority Queue) · Depth-First Search · Breadth-First Search
Problem
A network has n nodes, numbered 1 to n. The list times describes its links: [u, v, w] means a signal sent from node u reaches node v exactly w time units later. Links are one-way, and a link can have a delay of 0.
At time 0, node k sends a signal. Every node that receives it passes it on along all of its outgoing links at once. Return the time at which the last node receives the signal. If some node never receives it, return -1.
A node hears the signal at the earliest moment any path from k delivers it, so the answer is the largest shortest-path time from k over all nodes.
Examples
Input: times = [[1,2,4],[1,3,1],[3,2,2],[2,4,1]], n = 4, k = 1 Output: 4
Node 3 hears at time 1. Node 2 could hear at 4 over the direct link, but the path 1 → 3 → 2 delivers it at 3. Node 4 hears at 3 + 1 = 4, the latest of all.
Input: times = [[1,2,5]], n = 3, k = 1 Output: -1
No link leads to node 3, so it never receives the signal.
Input: times = [[2,1,3]], n = 2, k = 1 Output: -1
The only link goes from 2 to 1. A signal starting at 1 cannot travel it backwards.
Constraints
- 1 <= k <= n <= 100
- 0 <= len(times) <= 6000
- times[i] = [u, v, w] with 1 <= u, v <= n and u != v
- 0 <= w <= 100
- no pair (u, v) appears twice
Approaches
- Baseline: Bellman-Ford — time O(V · E), space O(V)
Follow-up
What if some delays could be negative (but no cycle has a negative total)? Dijkstra’s “smallest is final” rule breaks, and Bellman-Ford, the baseline here, becomes the right tool. And if the same network is asked about from every possible start node, Floyd-Warshall answers all pairs in O(V³).
Related problems
Start free on Cariara · Coding problems · System design studio
