Lesson 46 — Graphs VI: Dijkstra, BFS with weights

~20 minutes · Day 57 · Dijkstra · Python

Tonight you meet Network Delay Time: a signal starts at one node, travels along directed weighted edges, and you need the time when every node has received it. Interviewers like this because plain BFS is almost right, but edge weights change the meaning of “next.”

The invariant

Dijkstra is BFS with a priority queue: always settle the closest unsettled node, because no cheaper path to it can appear later.

That one sentence is the pattern. BFS uses a queue because every edge has the same cost. Dijkstra keeps the same expanding-frontier idea, but the frontier is ordered by total distance so far. The algorithm applies to graphs with non-negative edge weights (Wikipedia: Dijkstra's algorithm), and Network Delay Time gives positive travel times in its problem statement.

Edge labels are travel times. A plain BFS queue would settle B and C together; Dijkstra's min-heap settles the one with the smaller running total first.

What Python gives you

Python's heapq module gives a min-heap. That means heapq.heappop(heap) removes the smallest item. For Dijkstra, store pairs like (time_so_far, node), so the next pop is always the closest unsettled node.

Network Delay: the slow way first

The brute force idea is repeated relaxation: scan every edge again and again, updating a node whenever you find a cheaper route to it. That works for this positive-weight problem, but it wastes time revisiting edges whose start node is not the closest useful frontier. In the worst case, repeated relaxation takes O(VE) time for V nodes and E edges.

Dijkstra asks a sharper question: instead of scanning everything, which currently reachable node has the smallest known time? A min-heap answers that question directly.

Network Delay: the Dijkstra way

import heapq

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times: graph[u].append((v, w))  # directed weighted edge
    dist, heap = {}, [(0, k)]                       # settled times, frontier
    while heap:
        time, node = heapq.heappop(heap)            # closest unsettled node
        if node in dist: continue                   # skip stale path
        dist[node] = time                           # first pop settles node
        for nei, w in graph[node]:
            heapq.heappush(heap, (time + w, nei))   # extend frontier
    return max(dist.values()) if len(dist) == n else -1

The trust point is dist[node] = time. The first time a node leaves the heap, it has the smallest unsettled distance. Because all edge weights are positive, any later route to that same node must come through a path that is no cheaper.

Watch C fall from 5 to 3 and D from 9 to 5 as settling B then C relaxes their edges; the settled set grows one closest node per pop.

Transfer: same frontier, new costume

A delivery app has cities as nodes and road times as edge weights. From city A, return the fastest time to reach every other city.

Before opening the reveal: should the frontier be a normal queue or a min-heap? What should each heap item contain?

What the trade buys you

The memory stores the graph, settled distances, and heap frontier. The win is that the heap keeps the next useful node at the top instead of making you scan the whole graph to find it.

Practice — answer before you scroll past

time, node = heapq.heappop(heap)
dist[node] = time
for nei, w in graph[node]:
    heapq.heappush(heap, (time + w, nei))

Your move (tonight)

Solve Network Delay Time on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Predict: name the node, the edge, the start node, and why plain BFS is not enough.
2. Attempt: build the adjacency list, then code the heap loop from memory.
3. Compare: check whether your reasoning settles nodes at the same moment as the solution.
4. Encode: write the invariant from this page in your own words.