DSAMotivator

Network Delay Time

Medium·🛰️ Advanced Graphs·Open on LeetCode ↗

A signal starts at one node and travels along directed edges that each take some time. Find how long until every node has received it, or report that some node never does.

times = [[1,2,2],[1,3,5],[2,3,1],[2,4,4],[3,4,2]], n = 4, k = 1step 1/13
251421∞2∞3∞4∞

The signal starts at 1. Every other node's best known time is still infinity.

1import heapq
2from collections import defaultdict
3 
4def network_delay_time(times, n, k):
5    graph = defaultdict(list)
6    for u, v, w in times:
7        graph[u].append((v, w))
8 
9    dist = {}
10    heap = [(0, k)]
11    while heap:
12        d, node = heapq.heappop(heap)
13        if node in dist:
14            continue
15        dist[node] = d
16        for nei, w in graph[node]:
17            if nei not in dist:
18                heapq.heappush(heap, (d + w, nei))
19 
20    return max(dist.values()) if len(dist) == n else -1
Read the 13 steps as text
  1. 1The signal starts at 1. Every other node's best known time is still infinity.
  2. 21 is the closest unfinished node at 0. Nothing found later can beat that, so settle it.
  3. 3Reach 2 via 1 in 0 + 2 = 2. First route found.
  4. 4Reach 3 via 1 in 0 + 5 = 5. First route found.
  5. 52 is the closest unfinished node at 2. Nothing found later can beat that, so settle it.
  6. 6Reach 3 in 3, beating the 5 already queued. The old entry stays but is now stale.
  7. 7Reach 4 via 2 in 2 + 4 = 6. First route found.
  8. 83 is the closest unfinished node at 3. Nothing found later can beat that, so settle it.
  9. 9Reach 4 in 5, beating the 6 already queued. The old entry stays but is now stale.
  10. 103 was already settled — this is a stale heap entry. Discard it.
  11. 114 is the closest unfinished node at 5. Nothing found later can beat that, so settle it.
  12. 124 was already settled — this is a stale heap entry. Discard it.
  13. 13All 4 nodes settled. The slowest is 5, so that's when the whole network has the signal.

The idea

The phrasing hides a standard problem. 'When has everyone received it' is the *slowest* of the shortest delivery times — so this is single-source shortest paths, and then a max over the results. Recognising that is most of the work.

Edge weights are positive, which is exactly the condition Dijkstra needs. Plain BFS would be wrong here: BFS finds the path with the fewest edges, and the fewest edges is not the least time. In the sample below, 1→3 is one edge costing 5, while 1→2→3 is two edges costing 3.

Dijkstra's insight is that if you always expand the closest unfinished node, then the moment you pop a node its distance is final. Nothing discovered later can improve it, because every other route out of the frontier is already at least as long and edges only add. That's why the algorithm can settle a node permanently instead of revisiting it.

The heap is what makes 'closest unfinished node' cheap. The `if node in dist: continue` line is the other half — a node can be pushed several times with different tentative distances, and this discards the stale copies without ever needing to delete from the heap.

The approach

  1. 1Build an adjacency list from the edge list.
  2. 2Push (0, source) onto a min-heap keyed by distance, and keep a dict of settled distances.
  3. 3Pop the smallest. If that node is already settled, discard it and continue — it's a stale entry.
  4. 4Otherwise settle it at that distance, and push (distance + weight, neighbour) for each unsettled neighbour.
  5. 5When the heap empties, every reachable node is settled. If any node is missing, return -1; otherwise return the largest settled distance.

Complexity

Time
O(E log V)
Space
O(V + E)

Each edge can push at most one heap entry, and each push or pop costs log of the heap size. The space is the adjacency list plus the heap.

Code

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    dist = {}
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue
        dist[node] = d
        for nei, w in graph[node]:
            if nei not in dist:
                heapq.heappush(heap, (d + w, nei))

    return max(dist.values()) if len(dist) == n else -1

What goes wrong

  • •Using BFS because the weights look small. It finds fewest-edges, not least-total-weight, and quietly returns a wrong answer on any graph where a longer route is cheaper.
  • •Forgetting the stale-entry check. Without it a node gets settled more than once, and the second, larger distance overwrites the correct one.
  • •Returning the sum of the distances, or the distance to the last node popped. The answer is the maximum over all of them — the signal isn't done until the slowest node has it.
  • •Missing the unreachable case. If fewer than n nodes end up settled the answer is -1, and checking `len(dist) == n` is easier to get right than tracking reachability separately.
  • •Reaching for Dijkstra reflexively on a graph with negative weights. The settle-once argument collapses there, and the answer becomes Bellman-Ford.