Network Delay Time
A network has n nodes labelled 1 to n. Link times[i] = [u, v, w] carries a signal from node u to node v in w units of time, in that direction only.
A signal leaves node k at time 0 and travels along every link it can. Return the time when the last node receives it, or -1 if some node never does.
Function
- timesinteger-2d-array
- the directed links, each as [u, v, w]
- ninteger
- the number of nodes
- kinteger
- the node that sends the signal
- Returnsinteger
- the time when the last node receives the signal, or -1
Constraints
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ nandu ≠ v0 ≤ w ≤ 100- No two links share both the same
uand the samev. 1 ≤ k ≤ n
Examples
- Input
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Output
- 4
- Explanation
- The direct link reaches node 2 at time 4, but the route through node 3 arrives at 1 + 2 = 3. Node 4 hears the signal last, at 3 + 1 = 4.
- Input
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Output
- -1
- Explanation
- Node 2 hears the signal at time 3, but the only link touching node 3 runs from 3 to 1. Node 3 never hears it, so the answer is -1.
- Input
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Output
- 2
- Explanation
- The link to node 3 takes 0, so node 3 hears the signal at time 0. Node 1 then hears it at 0 + 2 = 2, sooner than the 5 of its direct link.
Follow-up
Suppose the signal fades after crossing m links. How do you find the time the last node hears it under that limit?
Hints
Open them one at a time. Each one gives away a little more.
A node receives the signal at the length of the fastest route to it from
k. So the answer is the largest of those fastest times, or -1 when some node has no route at all.No link takes negative time. So among the nodes whose time is not final yet, the one with the smallest tentative time cannot get any faster: every other route to it passes through another of those nodes, which is reached no sooner. Settle the nodes in order of arrival.
Keep a min-heap of
(time, node)pairs. Pop the smallest, skip it if the node already has a smaller time, and push every neighbour whose time improves. When the heap is empty, take the largest time.
Solution
Each node hears the signal at the length of its fastest route from k, so this is single source shortest paths followed by a maximum, or -1 when a node has no route. Link times are never negative, so Dijkstra's algorithm settles each node once. Below, E is times.length.
Depth-first search that revisits on every faster route
Correct, but does not finish on the largest tests
Intuition
Search from k depth first, carrying the time so far, and record each node's fastest arrival. A route that reaches a node no sooner than its record stops; a sooner one improves the record and searches on. Every record ends at the true fastest time, because the fastest route improves it at some point.
A node can improve many times. Put 18 gates in a row, each pair joined by a free link and by a detour of 65,536, 32,768 and so on down to 1. Trying detours first, the search reaches the last gate at 131,072 different times and walks everything behind it each time: work exponential in n.
Algorithm
- Set every best time to infinity and push
(k, 0)on a stack. - Pop
(node, t). Skip it unlesst < best[node]; then setbest[node] = t. - Push
(next, t + w)for every link fromnodewhose arrival beatsbest[next]. - When the stack is empty, return -1 if any best time is infinite, otherwise the largest.
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
best = [INF] * (n + 1) # the fastest arrival found so far at each node
stack = [(k, 0)]
while stack:
node, t = stack.pop()
# A route that is not faster than one already found adds nothing.
if t >= best[node]:
continue
best[node] = t
# Push in reverse so the first listed edge is explored first.
for nxt, w in reversed(graph[node]):
if t + w < best[nxt]:
stack.append((nxt, t + w))
worst = 0
for node in range(1, n + 1):
if best[node] == INF:
return -1
worst = max(worst, best[node])
return worstBellman-Ford: relax every link up to n-1 times
Intuition
Keep a tentative time dist per node, 0 for k. Relaxing a link u → v lowers dist[v] to dist[u] + w when that is smaller. Bellman-Ford relaxes every link in each pass.
Take the fastest route to a node, say k → a → b → v. The first pass makes dist[a] final, the second dist[b], the third dist[v]. A fastest route never repeats a node, so it has at most n-1 links, and n-1 passes settle every node.
Each pass costs O(E). A 3,000 node chain listed from its far end back takes 2,999 passes over 4,000 links: about 12 million relaxations.
Algorithm
- Set
dist[k] = 0and every otherdistto infinity. - Repeat up to n-1 times: for every link
[u, v, w], ifdist[u] + w < dist[v], setdist[v] = dist[u] + w. - Stop early after a pass that changes nothing.
- Return -1 if any
distis still infinite, otherwise the largest one.
def networkDelayTime(times, n, k):
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
# A fastest route visits each node at most once, so it has at most n-1 edges,
# and n-1 passes over every edge are enough to find it.
for _ in range(n - 1):
changed = False
for u, v, w in times:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # a pass that improves nothing means every time is final
break
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worstDijkstra's algorithm with a min-heap
Intuition
Among the nodes not settled yet, the one with the smallest tentative time is already final. Any other route to it must leave the settled nodes through an unsettled node whose time is at least as large, and the links after that only add time, because none is negative. So you settle that node, relax its links once, and repeat.
A min-heap finds the smallest time. When a node improves, push a new entry and leave the old one in place; a popped entry whose time is above dist is stale, so you skip it. Each link pushes at most one entry, so the heap holds at most E + 1 entries and the total is O(E log E).
Algorithm
- Set
dist[k] = 0, every otherdistto infinity, and push(0, k)on a min-heap. - Pop the smallest
(t, node); ift > dist[node], skip it as stale. - For each link
node → nextwith timew, ift + w < dist[next], setdist[next] = t + wand push(t + w, next). - When the heap is empty, return -1 if any
distis infinite, otherwise the largest.
import heapq
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
heap = [(0, k)] # (arrival time, node), smallest time on top
while heap:
t, node = heapq.heappop(heap)
# A stale entry: this node was already reached sooner.
if t > dist[node]:
continue
# t is now final: every other route reaches node later.
for nxt, w in graph[node]:
if t + w < dist[nxt]:
dist[nxt] = t + w
heapq.heappush(heap, (t + w, nxt))
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worst
Pitfalls and edge cases
- Treating links as two way.
[3, 1, 2]carries the signal from 3 to 1 only, so node 3 never hears it in the second example. - Using plain breadth-first search. It finds the route with the fewest links: in the first example it gives node 2 time 4 instead of 3.
- Forgetting the -1. Taking the maximum without a check returns infinity, or hides the node that never heard the signal.
- Using the largest int as infinity.
dist[u] + wthen wraps to a negative number for an unreachedu; skip unreached nodes or use 10^9.
Frequently asked questions3
What is the time complexity of Network Delay Time?
With Dijkstra's algorithm and a binary heap it is O(E log E), where E is the number of links. That equals O(E log n), since E is at most n². The space is O(n + E). Bellman-Ford takes O(n · E) time.
Why does Dijkstra's algorithm need non-negative weights?
Dijkstra never revisits a settled node, which is safe only if no later route can be shorter. With links A → B of time 2, A → C of time 3 and C → B of time -2, it settles B at 2, yet the route through C reaches it at 1. Bellman-Ford handles negative times.
Can you solve Network Delay Time without a heap?
Yes. Dijkstra with a plain array scans every unsettled node for the smallest time, which costs O(n²) in total. It wins on dense graphs, where E is close to n². On sparse graphs, such as 3,000 nodes and 4,000 links, the heap version does far less work.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def networkDelayTime(times, n, k):
# Write code hereTest #1
Test #2
Test #3
Arguments
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Expected Output
4