Network Delay Time
A network has n nodes, labelled from 1 to n. You get its links as a list times, where times[i] = [u, v, w] means a signal sent from node u reaches node v after w units of time. Links work in one 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
- Node 3 hears the signal at time 1. Node 2 could hear it at 4 over its direct link, but the route through node 3 arrives at 1 + 2 = 3, and node 4 hears it at 3 + 1 = 4. Node 4 is last, at time 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 that touches node 3 runs from 3 to 1, the wrong way. 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, together with node 2. Node 1 then hears it at 0 + 2 = 2, sooner than the 5 of its direct link, so every node has the signal at time 2.
+16 hidden tests on Submit
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 the task is single source shortest paths in a directed graph, followed by a maximum. The answer is the largest shortest time, or -1 when some node has no route. The link times are never negative, which is what lets Dijkstra's algorithm settle each node once, in order of arrival, with a min-heap. Below, E is the number of links, times.length.
Depth-first search that revisits on every faster route
Correct, but does not finish on the largest tests
Intuition
Start a search at node k with time 0 and follow every link, carrying the time so far. Record, for each node, the fastest arrival seen. When the search reaches a node no sooner than its record, stop there: anything that route could offer further on, the faster route already offered. When it reaches the node sooner, the record improves, and everything behind the node might improve too, so the search goes on from it.
This is always correct. The search only stops when no route improves any record, and the fastest route to every node improves that node's record at some point, so every record ends at the true fastest time.
The trouble is how many times a node can improve. A depth-first search follows the first link it meets all the way down, so it can reach a node by a slow route, then a slightly faster one, then a faster one again, and walk everything behind the node each time. Picture 18 gates in a row. Between each pair of gates you can take a free link or a detour, a chain of links whose times add up to 65,536, 32,768 and so on down to 1. Trying detours first, the search reaches the last gate at 131,072 different times, each one sooner than the last, and walks the 1,700 nodes behind it every time: about 220 million steps. Two of the large tests are built this way, one with each detour listed before its free link and one with it listed after, so a search trips on one of them whichever order it tries links in.
Algorithm
- Build an adjacency list: for every node, the links leaving it with their times.
- Set every node's best time to infinity and push
(k, 0)on a stack. - Pop
(node, t). Iftis not belowbest[node], skip it; otherwise 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 still infinite, otherwise the largest one.
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 for every node: 0 for k, infinity for the rest. Relaxing a link u → v with time w means: if dist[u] + w is below dist[v], the link offers a faster way into v, so lower dist[v] to it. Bellman-Ford makes passes over the whole list and relaxes every link in each pass.
Why does that end with the right times? Take the fastest route to some node, say k → a → b → v. The first pass relaxes k → a while dist[k] is already 0, so after it dist[a] is final. The second pass makes dist[b] final, the third dist[v]. A fastest route never needs to visit a node twice, since a loop never takes negative time, so it has at most n-1 links, and n-1 passes settle every node. A pass that changes nothing proves that no later pass can, so you stop there.
Each pass costs O(E), so the worst case is O(n · E). The order of the list decides how bad it gets: if the links of one long route are listed from its far end back to the start, each pass settles one more node. One large test is exactly that, a 3,000 node chain listed backwards, which takes 2,999 passes over 4,000 links: about 12 million relaxations. That still runs in time at this size, but the work grows with n times E. Bellman-Ford's strength lies elsewhere: it stays correct when some link times are negative, where Dijkstra fails.
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
Bellman-Ford wastes passes because it relaxes the links out of nodes whose times are not final yet, and must come back to them. Dijkstra's algorithm relaxes the links of each node exactly once, at the moment its time is final. The question is how to know when that is.
The answer is a greedy rule: 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 at some point, through an unsettled node whose time is at least as large, and the links after that can only add time, because none is negative. So you settle that node, relax its links, and repeat. In the first example node 1 settles at 0 and offers node 2 time 4 and node 3 time 1. Node 3 is smallest, settles at 1, and lowers node 2 to 3. Node 2 settles at 3 and offers node 4 time 4, which settles last. The answer is 4.
A min-heap finds the smallest tentative time fast. Push (time, node) whenever a node's time improves, and leave the older entry in the heap instead of hunting for it. When the older entry comes out later, its time is above the node's current time, so you skip it. Each link pushes at most one entry, so the heap never holds more than E + 1 entries, and each push or pop costs O(log E). That makes O(E log E) in total, with O(n + E) space for the adjacency list, the times and the heap.
Non-negative times are what make the greedy rule safe. Take links A → B with time 2, A → C with time 3 and C → B with time -2. Dijkstra settles B at 2, yet the route through C reaches it at 1. A signal can never arrive before it is sent, so every time here is at least 0 and the rule holds.
Algorithm
- Build an adjacency list of
(next, w)pairs for every node. - Set
dist[k] = 0, every otherdistto infinity, and push(0, k)on a min-heap. - Pop the smallest
(t, node). Ift > dist[node], the entry is stale: skip it. - Otherwise
tis final. For each link fromnodetonextwith 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 one.
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
Most bugs ignore the direction of the links, trust the first time offered to a node, or lose track of nodes the signal never reaches.
- Treating links as two way.
[3, 1, 2]carries the signal from 3 to 1 only, which is why node 3 never hears it in the second example. - Using plain breadth-first search. It finds the route with the fewest links, not the fastest one: in the first example it gives node 2 time 4 over the direct link instead of 3 through node 3.
- Marking a node final when it is pushed instead of when it is popped. The first time offered to a node is not always its best; only the smallest entry popped from the heap is final.
- Forgetting the -1. Taking the maximum without checking either returns infinity or reports the largest finite time and hides the node that never heard the signal.
- Counting nodes from 0. Nodes are labelled 1 to n, so size the arrays
n+1and leave the unused slot 0 out of the maximum. - Overflow from infinity. If infinity is the largest int,
dist[u] + wwraps around to a negative number for an unreachedu. Skip unreached nodes, or use a value such as 10^9 that leaves room.
Frequently asked questions4
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 is the same as O(E log n), since E is at most n². The adjacency list, the times and the heap take O(n + E) space. Bellman-Ford takes O(n · E) time and O(n) space.
Why does Dijkstra's algorithm need non-negative weights?
Dijkstra settles the node with the smallest tentative time and never looks at it again. That is only safe if no later route can be shorter, and with non-negative weights every route through an unsettled node costs at least that node's time. A negative link breaks the argument: a route through a node that looked more expensive can still end up cheaper. For negative weights, use Bellman-Ford.
Why not use BFS for Network Delay Time?
BFS visits nodes in order of how many links they are from the start, which matches arrival time only when every link takes the same time. Here link times differ, so a route with more links can arrive sooner. If every time were equal, BFS would be enough, and with times of only 0 and 1 a deque based 0-1 BFS works.
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 and needs no heap. That is the better choice on dense graphs, where E is close to n². On sparse graphs, like the large tests here with 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.
Python
def networkDelayTime(times, n, k):
# Write code hereCase 1
Case 2
Case 3
Input
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Expected
4