DSA sheet · Graphs · Dijkstra pattern

Network Delay Time

The second Dijkstra problem. The teacher's message is simple: if you understood the basic Dijkstra video, you can solve this one on your own. She literally copies the previous code and changes a handful of lines. The useful lessons are which lines change and why: the graph is directed, the nodes start at 1, and instead of returning the whole distance list we return its largest value, or −1 if some node can never be reached.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Dijkstra, then take the maximum
• Part B · Revision page

Part 0 · Before starting

Directed, weighted graphs

A graph is nodes (circles) joined by edges (lines). Here the edges are directed: an edge u → v is a one-way road. You can go from u to v, but not back from v to u unless a separate edge v → u is given. Each edge also has a weight, here a travel time.

        1
  (2) ———→ (1)        2 can send to 1 in 1 unit of time,
                      but 1 cannot send back to 2

Building the adjacency list (one direction only)

The input is an edge list times of [u, v, w]. We turn it into an adjacency list: for each node, the list of (next node, time) it can send to. For a directed graph we add the edge only from u. (In the undirected Dijkstra problem we added both directions.)

n = 4
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]

graph = [[] for _ in range(n + 1)]   # index 0 unused, nodes are 1..n
for u, v, w in times:
    graph[u].append((v, w))          # one way only: u -> v

print(graph)   # [[], [], [(1, 1), (3, 1)], [(4, 1)], []]

Visited, BFS and why we need Dijkstra here

In unweighted graphs a BFS with a visited array gives shortest distances, because every edge costs the same. Here edges have different times, so the route with fewer edges is not always the faster one. That's why we use Dijkstra: BFS with a min-heap instead of a queue, and "go again only if the new time is smaller" instead of a visited array. Full explanation, including a picture of plain BFS going wrong, is on the Dijkstra page.

The Dijkstra code we start from

import heapq

def dijkstra(V, edges, src):
    graph = [[] for _ in range(V)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    dist = [float('inf')] * V
    dist[src] = 0
    pq = [(0, src)]                         # (distance, node), smallest first
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:                  # stale entry
            continue
        for nei, w in graph[node]:
            if d + w < dist[nei]:           # better route found
                dist[nei] = d + w
                heapq.heappush(pq, (d + w, nei))
    return dist

print(dijkstra(3, [[0, 1, 1], [1, 2, 3], [0, 2, 6]], 2))   # [4, 3, 0]

Part A · Dijkstra, then take the maximum

LeetCode 743

1The question in simple words

There are n computers (nodes) labelled 1 to n. times[i] = [u, v, w] means a signal sent from u reaches v after w units of time. The edges are one way. We send a signal from node k. It spreads along every edge at the same time. Return how long it takes until every node has received it. If some node never gets it, return −1.

Her example (LeetCode example 1): times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2.

            1
     (2) ———————→ (1)
      |
     1|
      ↓       1
     (3) ———————→ (4)

Answer: 2.

k is just the source under a different name. As she keeps reminding us, a graph has no built-in starting point like a tree's root or a list's head, so the question has to name one.

2What the constraints tell us

• Nodes are numbered 1..n (the previous problem used 0..V−1) → the dist list needs size n + 1, and loops run from 1 to n inclusive.
• Edges are directed → add each edge one way only.
• Times are ≥ 0 → Dijkstra is allowed (no negative edges). It also means no answer can be below 0, so starting the running maximum at 0 is safe.
• n ≤ 100 and at most 6000 edges: small, so O((V + E) log V) is easily fast enough.
• The return type is a single integer, not a list. That's the other change from the last problem.

3Intuition

The signal travels down every edge at once, like water poured into pipes. Each node gets the signal at the earliest moment any route reaches it, which is exactly its shortest distance from k. So:

• run Dijkstra from k to get every node's arrival time,
• everyone has the signal once the last node gets it → the answer is the maximum of the shortest distances,
• if any node still has distance "infinity", the signal never got there → −1.

4Building the logic from her example

Why "minimum time" becomes a maximum

The words are confusing at first: the question asks for the minimum time, but we return a maximum. She works it out on the example: after 0 units only node 2 has it; after 1 unit nodes 1 and 3 have it, but 4 doesn't; after 2 units all four have it. The earliest moment when all nodes are covered is the arrival time of the slowest node.

• Minimum is already inside each dist[i]: the fastest way to reach node i.
• Maximum is across the nodes: we must wait for the last one.

Her dist array for the example (index 0 unused): [–, 1, 0, 1, 2] → the max of indexes 1..4 is 2.

When is the answer −1?

She changes the picture: suppose node 4 had no edge coming into it. Then nothing can ever reach it and its dist stays at the starting "infinity". So while we scan for the maximum, if we see an infinity, we return −1 at once.

  (2) ——1——→ (1)
   |
   1                  (4)   ← no edge comes in
   ↓
  (3)

  dist = [–, 1, 0, 1, ∞]  → some node unreached → −1

LeetCode example 3 shows the same thing from the other side: times = [[1,2,1]], n = 2, k = 2. The only edge goes from 1 to 2. Starting at 2 there is no way back to 1 (one-way road), so the answer is −1.

What changes from the previous code (her "copy and edit" list)

Everything else (heap of (time, node), stale check, relax if smaller) is unchanged.

5Approach steps

1. Build a directed adjacency list of size n + 1 from times.
2. dist = [inf] * (n + 1), dist[k] = 0, heap = [(0, k)].
3. Run Dijkstra: pop the smallest, skip stale entries, relax each outgoing edge.
4. Set ans = 0. For each node i from 1 to n: if dist[i] is infinity, return −1; otherwise ans = max(ans, dist[i]).
5. Return ans.

6Code (Python)

import heapq

class Solution:
    def networkDelayTime(self, times, n, k):
        graph = [[] for _ in range(n + 1)]      # nodes 1..n
        for u, v, w in times:
            graph[u].append((v, w))             # directed: u -> v only

        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        pq = [(0, k)]                           # (time, node)

        while pq:
            t, node = heapq.heappop(pq)
            if t > dist[node]:                  # stale entry
                continue
            for nei, w in graph[node]:
                nt = t + w
                if nt < dist[nei]:
                    dist[nei] = nt
                    heapq.heappush(pq, (nt, nei))

        max_time = 0
        for i in range(1, n + 1):               # skip index 0, include n
            if dist[i] == float('inf'):         # never reached
                return -1
            max_time = max(max_time, dist[i])
        return max_time

7Code line by line

8Dry run: heap and dist after every pop

Run 1: her example (answer 2)

Adjacency: 2: (1,1) (3,1) · 3: (4,1). dist written as [node1, node2, node3, node4]. Start: dist = [∞, 0, ∞, ∞], heap = [(0,2)].

Scan 1..4: no infinity; max(1, 0, 1, 2) = 2 ✓.

On a tie like (1,1) and (1,3), Python compares the second item, so node 1 comes out first. Either order gives the same answer.

Run 2: an example with a better route found later (and a stale entry)

times = [[1,2,4],[1,3,1],[3,2,1],[2,4,1]], n = 4, k = 1.

           4
   (1) —————————→ (2) ——1——→ (4)
     \            ↑
     1\          /1
       ↘        /
          (3)

Start: dist = [0, ∞, ∞, ∞], heap = [(0,1)].

Scan: max(0, 2, 1, 3) = 3. Without the stale skip, pop 5 would recheck node 2's edge to 4 with time 5, fail the < test, and waste a little work. The answer would still be 3.

Run 3: unreachable node (answer −1)

times = [[1,2,1],[2,3,1]], n = 4, k = 1. Pops: (0,1) → dist[2] = 1; (1,2) → dist[3] = 2; (2,3) → no edges; heap empty. dist (1..4) = [0, 1, 2, ∞]. The scan hits node 4 = ∞ → −1.

9Complexity & remember

• Time O((V + E) log V), the same as Dijkstra (here V = n, E = len(times)): about V + E heap entries, each costing log for push and pop. The final scan is only O(V).
• Space O(V + E) for the graph and the heap, plus O(V) for dist. One small saving over the last problem: no extra result list, because we return a single number.

Part B · Revision page

s = Solution()
print(s.networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))             # 2
print(s.networkDelayTime([[1, 2, 1]], 2, 1))                                  # 1
print(s.networkDelayTime([[1, 2, 1]], 2, 2))                                  # -1
print(s.networkDelayTime([[1, 2, 4], [1, 3, 1], [3, 2, 1], [2, 4, 1]], 4, 1)) # 3
print(s.networkDelayTime([], 1, 1))                                           # 0

Based on this video: Network Delay Time