These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers advanced graphs: Dijkstra’s shortest paths, Prim’s and Kruskal’s minimum spanning trees, topological sort with Kahn’s algorithm, and Bellman-Ford for paths with an edge budget.
Plain graphs ask whether you can get somewhere. Advanced graphs ask what it costs, what it costs to connect everything, or what order things may come in, and every algorithm here repeats one step: finalise the node you can prove is safe, then update its neighbours. Most wrong answers in this topic come from using that step where its proof doesn’t hold.
The topic builds on Heap / Priority Queue and Graphs (DFS, BFS, 3-colour cycle detection and Union-Find live there and are only referenced here), and nothing later in the series builds on it. The prerequisites here are Dijkstra’s, Prim’s, Kruskal’s and Topological Sort. I’ve added Bellman-Ford at the end, because one of the problems limits how many edges a path may use.
How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.
Dijkstra’s
Foundation
Picture a fire starting at the source and spreading along every road at the same speed. Each town catches fire at the time given by its shortest distance, and towns catch fire in order of that distance. Dijkstra’s algorithm simulates this: it always handles the unhandled town that is closest to the source.
It solves single-source shortest paths when every edge weight is non-negative. BFS from Part 14 is the special case where all weights are equal.
Mechanics
Keep dist[v], the best distance found so far, plus a min-heap of (distance, node) candidates. Repeat:
- Pop the smallest
(d, u). - If
uis already settled, this entry is stale, so skip it. - Otherwise settle
u:dis final. - For every edge
u -> vof weightw, ifd + w < dist[v], setdist[v] = d + wand push(d + w, v).
The invariant. When (d, u) is the smallest entry in the heap and u is unsettled, d is the true shortest distance to u. Why this is safe: any other path to u has to leave the settled set at some point, through an edge into some unsettled node x. The cost of reaching x is at least the smallest heap key, and that is d. Everything after x adds weights that are ≥ 0. So no other path costs less than d. The whole proof depends on the “≥ 0”. A negative edge after x could pull the total below d, which is why Dijkstra is wrong with negative weights.
Stale entries (lazy deletion). Python’s heapq can’t lower an existing key (recalled: it has no decrease-key), so when a better distance turns up we just push a second entry. The older, larger entry stays in the heap and gets skipped when it is popped.
Worked example: a directed graph, source 0.
Edges: 0->1 (4), 0->2 (1), 2->1 (2), 1->3 (1), 2->3 (5), 3->4 (3).
The direct edge 0->1 costs 4, but 0->2->1 costs 1 + 2 = 3. Node 3 is first reached through 0->2->3 for 1 + 5 = 6, then improved through 0->2->1->3 to 3 + 1 = 4. Node 4 gets 4 + 3 = 7. Final distances: [0, 3, 1, 4, 7].
Diagram
Heap trace, taken from running the code below. Heap contents are shown after that step’s pushes.
Steps 4 and 6 are the lazy-deletion entries. Node 1 was first pushed at 4 and node 3 at 6, and both were improved before those entries came up.
Implementation
import heapq
from collections import defaultdict
def dijkstra(n, edges, src):
graph = defaultdict(list) # u -> [(v, w)], directed
for u, v, w in edges:
graph[u].append((v, w))
dist = {src: 0} # best distance found so far
done = set() # nodes whose distance is final
heap = [(0, src)] # (distance, node); recalled: heapq is a min-heap
while heap:
d, u = heapq.heappop(heap)
if u in done:
# stale: u was settled earlier with a smaller d
# (example: (4,1) popped after node 1 was settled at 3)
continue
done.add(u) # d is final: every other path to u costs >= d
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
# strictly better: record it and push a fresh entry;
# the old, larger entry for v becomes stale
# (example: 2->1 gives 3 < 4, so (3,1) is pushed and (4,1) goes stale)
dist[v] = nd
heapq.heappush(heap, (nd, v))
return [dist.get(i, float("inf")) for i in range(n)]
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print(dijkstra(5, edges, 0)) # [0, 3, 1, 4, 7]
Edge cases I ran: a single node gives [0], an unreachable node stays inf ([0, 2, inf] for one edge 0->1 (2) among 3 nodes), zero-weight edges work ([0, 0, 0]), and parallel edges keep the cheaper one.
Complexity. V = nodes, E = edges. Each edge pushes at most once, so the heap holds at most E + 1 entries and each push or pop costs O(log E). Total time is O((V + E) log E), which is the same as O((V + E) log V) because log E ≤ 2 log V. Space is O(V + E).
Recognition
Signals:
- The question asks for a minimum total cost, time or distance from one source, and edge weights differ and are non-negative.
- A grid or state space where moves cost different amounts. The “graph” can be implicit, with nodes as states and edges as moves.
- The cost of a path is built by adding up its steps, or more generally by any rule that never gets cheaper as the path gets longer.
When not to use it:
- All weights are equal. Plain BFS gives the answer in O(V + E).
- Some weights are negative. The proof breaks, and you need Bellman-Ford (last module).
- The path has a limit on how many edges it may use. Dijkstra settles each node once at its cheapest cost, and that cheapest path might use too many edges. This also goes to the last module.
- You need all pairs of nodes on a small graph. Floyd-Warshall is simpler there (not needed for this list).
On the list, Network Delay Time shows the plain signal. Swim In Rising Water shows the “cheapest path under a cost rule you have to define” signal, where the cost isn’t a plain sum. Min Cost to Connect All Points looks like a Dijkstra problem because it says “min cost”, but it asks for something else (see Prim’s).
Pitfalls
- Settling on push instead of on pop. In the example, node 3 is first pushed at 6. If you finalised it then, you would keep 6 instead of 4.
- Missing the stale check. Without
if u in done, the stale(4,1)would relax node 1’s edges a second time. Here that does no harm, but with many improvements per node the same edges get relaxed over and over and the time blows up. - Negative edges. On
0->1 (2),0->2 (3),2->1 (-2),1->3 (1), the code returnsdist[3] = 3, but the true answer is 2 (0→2→1→3 = 3 − 2 + 1). Node 1 was settled at 2 before the negative edge was seen, and node 3 had already been relaxed from that wrong value. - Unreachable nodes. Decide what
infmeans for your answer before returning it. - Undirected graphs. Add both directions.
Active Recall
- At step 3, the heap holds
(3,1)and(4,1). Why is it safe to finalise node 1 at 3 without ever looking at the(4,1)entry? - If you only need the distance to node 3, what is the earliest moment you can stop, and why is stopping when node 3 is first pushed wrong?
- Replace the heap with a plain FIFO queue and settle each node the first time it is dequeued. What does node 1 get?
- In the negative-edge example from Pitfalls, which sentence of the correctness proof fails?
Answer out loud or on paper first.
Mini-task
Skipped. Swim In Rising Water requires re-deriving why the settle-on-pop guarantee still holds under its own path-cost rule, so this technique gets exercised from scratch there.
Transfer test
A warehouse grid: moving onto a floor tile costs 1 second, and moving along a conveyor belt tile costs 0 seconds. You want the fastest time from the loading dock to every shelf. Would you use Dijkstra? Why?
Prim’s
Foundation
You have to cable together every office in a campus, and each possible cable has a price. You don’t care how far any office is from any other. You only want every office connected at the lowest total price. The cheapest such set of cables forms a tree (any cycle has a cable you could remove), called the minimum spanning tree (MST): V − 1 edges that touch every node.
Prim’s grows a single connected blob. It starts at any node and, every step, buys the cheapest cable that leaves the blob.
Mechanics
The cut property is what makes the greedy choice safe. Split the nodes into any two groups. The cheapest edge crossing between them belongs to some MST. Exchange argument: take an MST that doesn’t contain that edge e. Adding e creates a cycle, and the cycle must cross the split a second time through another edge f. f costs at least as much as e, so swapping f out for e gives a spanning tree that costs no more.
Prim’s always uses the split (blob, everything else), so the cheapest edge leaving the blob is always safe to take.
The loop has the same shape as Dijkstra’s, with one difference that matters: the heap key is the weight of the single edge, w, not the path total d + w. Prim’s asks “how cheap is it to attach this node to the tree?”, not “how far is this node from the start?”.
- Push
(0, start). - Pop the smallest
(w, u). Ifuis already in the tree, it’s stale, so skip it. - Add
uand addwto the total. - Push
(weight, v)for every edge to a nodevnot yet in the tree.
Worked example: an undirected graph with 5 nodes.
Edges: 0-1 (4), 0-2 (1), 1-2 (2), 1-3 (5), 2-3 (8), 3-4 (3), 2-4 (9).
The MST is 0-2 (1), 2-1 (2), 1-3 (5), 3-4 (3), with total 1 + 2 + 5 + 3 = 11.
Diagram
Prim’s trace starting at 0, with heap entries written (w, node, from):
Implementation
import heapq
from collections import defaultdict
def prim(n, edges):
graph = defaultdict(list)
for u, v, w in edges: # undirected: store both directions
graph[u].append((v, w))
graph[v].append((u, w))
in_tree = set()
total = 0
heap = [(0, 0)] # (edge weight, node); node 0 joins for free
while heap and len(in_tree) < n:
w, u = heapq.heappop(heap)
if u in in_tree:
# stale: u already joined by a cheaper edge
# (example: (4,1) popped after node 1 joined through 2-1 at weight 2)
continue
in_tree.add(u)
total += w # w is the cheapest edge crossing (tree, rest): cut property
for v, wv in graph[u]:
if v not in in_tree:
heapq.heappush(heap, (wv, v)) # key is the edge weight wv, NOT total + wv
# fewer than n nodes reached means the graph is disconnected: no spanning tree
return total if len(in_tree) == n else None
edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (3, 4, 3), (2, 4, 9)]
print(prim(5, edges)) # 11
Edge cases I ran: n = 1 gives 0, a disconnected graph gives None, and a triangle of equal weights gives 2. I also checked it against the Kruskal version from the next module on 300 random graphs, and the totals matched every time.
Complexity. O(E log E) time with the heap and O(V + E) space. On a dense graph where every pair of nodes has an edge, E is about V²/2, and a heap-free version that keeps a best[v] array and scans it for the minimum each round runs in O(V²) (recalled). That is better than O(V² log V) when the graph is complete.
Recognition
Signals: “connect all”, “every node must be reachable”, “minimum total cost to link”, undirected, no source node. The answer is one number for the whole network, not one per node.
Shortest-path trees and spanning trees are different things. On the same example, Dijkstra from 0 (treating edges as undirected) gives distances [0, 3, 1, 8, 10] using edges 0-2, 2-1, 1-3, 2-4, for a total edge weight of 17. The MST uses 3-4 instead of 2-4 and totals 11. The MST doesn’t try to keep node 4 close to node 0, so it pays 3 for node 4 instead of 9.
Min Cost to Connect All Points shows the “connect all, no source” signal on a complete graph, which is also where the dense-graph note above matters.
Pitfalls
- Using
d + was the key. That turns Prim’s into Dijkstra and gives the shortest-path tree (17 here), not the MST (11). - Adding
wbefore the stale check. The stale(4,1)would be counted and the total would come out 15. - Disconnected input. The loop ends with fewer than V nodes in the tree. Return a sentinel, not a partial sum.
- Directed graphs. MST is defined for undirected graphs. The directed version (arborescence) is a different algorithm.
Active Recall
- At step 4,
(4,1)is popped. Which cut-property argument already made node 1’s 2-weight edge the right one? - Run Prim’s from node 3 instead of node 0. Is the total still 11? Is the tree the same?
- At step 2, the first entries pushed for nodes 3 and 4 were the expensive
(8,3)and(9,4). Node 3 later joins at 5 and node 4 at 3. Why is pushing those expensive entries first harmless? - What does the heap hold at most, and why isn’t it just V entries?
Answer out loud or on paper first.
Mini-task
Included. Min Cost to Connect All Points is a direct MST instance, not a from-scratch derivation of this technique, so the mechanics need their own workout here.
A village has n houses numbered 1 to n. House i can get water by digging its own well for well[i-1], or by laying a pipe to another house. pipes lists (a, b, cost) for the pipes that can be laid, and water flows both ways along a pipe. Find the minimum total cost so that every house has water.
Example: well = [5, 4, 3, 6], pipes = [(1,2,2), (2,3,2), (3,4,1), (1,4,7)]. The answer is 8.
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
A data centre wants to pick links between racks so that every rack is connected, and the chosen links should have the largest possible total bandwidth. Would you use Prim’s? Why?
Kruskal’s
Foundation
Kruskal’s builds the same MST from the other direction. Instead of growing one blob, you sort all the cables by price and go down the list, buying each cable unless its two ends are already connected. Early on you have many small islands, and they merge until there is one.
Mechanics
- Sort the edges by weight.
- For each edge
(u, v, w): ifuandvare in different components, take it and merge the components. Otherwise skip it, because it would close a cycle. - Stop after V − 1 edges have been taken.
“Are they in the same component?” and “merge them” are exactly Union-Find’s find and union from Part 14. I’m not re-teaching it here. The version below uses path halving and union by size.
Why taking the edge is safe. When (u, v, w) is taken, consider the cut (u’s current component, everything else). Every edge cheaper than w has already been looked at. Each one was either taken, so it’s inside some component, or skipped because its ends were already in one component. Either way, no cheaper edge crosses this cut, so (u, v, w) is the cheapest crossing edge, and the cut property from Prim’s says it’s safe. The same cut property proves both algorithms. They just pick different cuts.
Why skipping is safe. A skipped edge joins two nodes that are already connected by edges no heavier than it, so it would only close a cycle.
Same worked example as Prim’s, sorted by weight.
Diagram
Kruskal’s takes 3-4 (3) before 1-3 (5). Prim’s took them the other way round because node 4 wasn’t reachable from its blob until node 3 had joined. The edges and the total (11) are the same.
Implementation
class DSU:
"""Union-Find (taught in Part 14): find with path halving, union by size."""
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # a and b already share a root: edge would close a cycle
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra # hang the smaller tree under the larger one
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def kruskal(n, edges):
dsu = DSU(n)
total, taken = 0, 0
for u, v, w in sorted(edges, key=lambda e: e[2]):
if dsu.union(u, v):
# u and v were in different components, so w is the cheapest edge
# crossing (u's component, rest): every lighter edge was already processed
total += w
taken += 1
if taken == n - 1: # a spanning tree on n nodes has exactly n-1 edges
break
# else: skipped (example: 0-1 at weight 4, both ends already in {0,1,2})
return total if taken == n - 1 else None # fewer than n-1 means disconnected
edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (3, 4, 3), (2, 4, 9)]
print(kruskal(5, edges)) # 11
Edge cases I ran: n = 1 gives 0 (zero edges are needed, and taken == n - 1 == 0 holds from the start), a disconnected graph gives None, and a triangle of equal weights gives 2.
Complexity. The sort costs O(E log E). The Union-Find operations are almost O(1) each (recalled: inverse Ackermann amortised, with path compression or halving plus union by size). Total time is O(E log E), and space is O(V + E): O(V) for the DSU plus O(E) for the sorted copy of the edges.
Recognition
Kruskal’s fits better than Prim’s when:
- The input is already an edge list, and you don’t want to build an adjacency list.
- You care about the order in which components merge as the allowed weight grows. Processing edges in increasing order answers questions like “which nodes are connected using only edges ≤ t?” for every t in a single pass.
- The graph is sparse. On a complete graph with about V²/2 edges, sorting them all is more expensive than dense Prim’s O(V²).
A useful property of the merge order: the moment two nodes first land in the same component, the weight of the edge being processed is the smallest possible value of the heaviest edge on any path between them. Keep it in mind for “minimise the worst single step” questions.
Pitfalls
- Forgetting to sort, or sorting by the wrong tuple field.
- Assuming the graph is connected. Check
taken == n - 1. - Hand-rolled Union-Find without path compression or union by size. It can degrade to O(V) per
findon a chain. - Node labels that aren’t
0..n-1. Map them to indices first, or back the DSU with a dict.
Active Recall
- At weight 4, why is
0-1skipped, and what does that skip say about the path between 0 and 1 in the tree? - Prim’s took
1-3before3-4, and Kruskal’s took them in the opposite order. Why do both still produce the same tree? - Why can the loop stop after V − 1 edges without looking at
2-3 (8)and2-4 (9)? - You run Kruskal’s on a graph with two separate islands. What do
totalandtakenlook like at the end, and what did you actually build?
Answer out loud or on paper first.
Mini-task
Included. No list problem requires deriving Kruskal’s from scratch, so the mechanics get their own workout here.
You have n items and the distance between every pair. Split them into exactly k non-empty groups so that the smallest distance between two items in different groups is as large as possible, and return that distance.
Example: points on a line at positions [0, 1, 3, 10, 11, 20], where distance is |a - b|. With k = 3, the answer is 7. With k = 2 it’s 9, and with k = 4 it’s 2.
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
A cluster of servers has links, and each link has a latency. Offline, you get a batch of queries: “can server a reach server b using only links with latency ≤ t?” Would you use Kruskal’s idea? Why?
Topological Sort
Foundation
A to-do list with “X must happen before Y” rules. A topological order lists every item so that each rule points forward. One exists exactly when the rules have no cycle, which means the graph is a DAG (directed acyclic graph).
Part 14 found cycles with 3-colour DFS. This module uses Kahn’s algorithm, which builds the order directly and detects a cycle by coming up short.
Mechanics
Step zero: turn constraints into edges. This is where most mistakes happen, before any algorithm runs.
- Direction. An edge points from what comes first to what comes after. “a needs b”, “b before a”, “a depends on b” and “b unlocks a” all become the edge
b -> a. Write down one example constraint and its arrow before you write any code. - Every item is a node, including items that appear in no constraint. They have indegree 0 and can go anywhere, but they still have to appear in the output.
- One piece of evidence gives one edge. Add only what the input directly states. Transitive facts (“a before b, b before c, so a before c”) don’t need their own edges, because the order will respect them anyway.
- Duplicates are harmless if the edge list and the indegree count are updated together. They break if you deduplicate one and not the other.
- Contradictions in the input show up as a cycle.
Kahn’s loop. indegree[v] is the number of v’s prerequisites that haven’t been placed yet.
- Put every node with
indegree == 0in a queue. - Pop
u, append it to the output, and decrementindegree[v]for each edgeu -> v. Anyvthat reaches 0 joins the queue. - If the output ends up shorter than the number of nodes, there is a cycle.
Why placing a zero-indegree node is safe: everything it depends on is already in the output, so no rule can point backwards to it later. Why “came up short” means a cycle: when the queue empties, every leftover node still has an unplaced prerequisite among the leftovers. Follow those prerequisites backwards from any leftover node. There are finitely many leftovers, so the walk eventually repeats a node, and that is a cycle.
Worked example: a build pipeline.
Items: fetch, lint, build, test, ship, docs.
Rules: lint needs fetch, build needs fetch, test needs build, ship needs test, ship needs lint. docs has no rules.
Edges: fetch->lint, fetch->build, build->test, test->ship, lint->ship.
Diagram
Kahn’s trace (FIFO queue), from running the code:
Implementation
from collections import deque
def topo_order(items, needs):
# needs: list of (a, b) meaning "a needs b first" -> edge b -> a
graph = {x: [] for x in items} # every item is a node, even with no constraints
indegree = {x: 0 for x in items}
for a, b in needs:
graph[b].append(a)
indegree[a] += 1 # added together with the edge, so duplicates stay consistent
queue = deque(x for x in items if indegree[x] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u) # safe: indegree[u] == 0, all of u's prerequisites are placed
for v in graph[u]:
indegree[v] -= 1 # u was one of v's unplaced prerequisites
if indegree[v] == 0: # v's last prerequisite just got placed
queue.append(v)
if len(order) < len(items):
return None # every leftover node sits on or behind a cycle
return order
items = ["fetch", "lint", "build", "test", "ship", "docs"]
needs = [("lint", "fetch"), ("build", "fetch"), ("test", "build"),
("ship", "test"), ("ship", "lint")]
print(topo_order(items, needs))
# ['fetch', 'docs', 'lint', 'build', 'test', 'ship']
print(topo_order(items, needs + [("fetch", "ship")]))
# None
Edge cases I ran: no items gives [], a single item gives ['a'], a duplicated rule ("a","b") twice still gives ['b', 'a'], and a self-rule ("a","a") gives None.
Complexity. O(V + E) time: each node is queued once and each edge is decremented once. O(V + E) space.
Recognition
Signals: “prerequisites”, “dependencies”, “must come before”, “order of tasks/courses/letters”, “is there a valid ordering”, “detect a circular dependency”. The input is a set of pairwise order constraints, and the output is either one full ordering or a yes/no answer about whether one exists.
Kahn versus DFS (Part 14): both run in O(V + E). Kahn gives you the cycle signal as a simple count, it lets you swap in a heap for the smallest-first order, and its queue length tells you whether the order is unique. DFS gives reverse postorder and fits naturally if you’re already doing a DFS.
On the list, Alien Dictionary shows the signal: an order you have to infer, where the edges are hidden in the input rather than handed to you.
Pitfalls
- Reversed edges. The code runs happily and returns a valid order for the reversed rules. Here that gives
['ship', 'docs', 'test', 'lint', 'build', 'fetch']: ship first, which is wrong. Nothing crashes, so this bug is silent. - Missing isolated nodes. If you build nodes only from the rules,
docsdisappears from the output. - Forgetting the length check. Without it, a cyclic input returns a partial order (
['docs']in the cycle example) as if it were an answer. - Deduplicating edges but not indegrees, or the other way round.
- Assuming uniqueness. Many orders are usually valid. If a question wants one specific order, it must say which one (for example, smallest first).
Active Recall
- After
fetchis popped, bothlintandbuildjoin the queue, buttestdoesn’t. Why? - Add the rule “fetch needs ship”. Trace what Kahn’s does, and explain why
docsstill gets placed. - Is the order for the pipeline unique? How could you tell from the trace alone?
- Replace the deque with a min-heap of names. What order do you get for the pipeline?
Answer out loud or on paper first.
Mini-task
Skipped. Alien Dictionary requires deriving its edges from the input from scratch, which is this module’s hard part, so we cover that reasoning when we solve it directly.
Transfer test
A spreadsheet where cells hold formulas that reference other cells. After an edit, you need to recompute every cell exactly once, after all the cells it references, and report an error if there’s a circular reference. Would you use a topological sort? Why?
Bellman-Ford and bounded-edge shortest paths
The problems below also need this: Cheapest Flights Within K Stops caps how many edges a path may use, and Dijkstra’s settle-once rule can’t respect that cap.
Foundation
Instead of a fire that settles each town once, think of rounds. In round 1 you know the cheapest way to reach anything with 1 edge. In round 2, you know it with up to 2 edges, built by extending round 1’s answers by one more edge. After r rounds you have the cheapest path using at most r edges. Nothing gets settled early, so there’s no greedy step for a negative edge or a hop limit to break.
Mechanics
Invariant: after round r, dist[v] = the minimum cost over all paths from src to v with ≤ r edges.
Round r: take a snapshot prev = dist[:], which holds round r − 1’s values. Then for every edge (u, v, w), if prev[u] + w < dist[v], set dist[v] = prev[u] + w.
Why the snapshot matters. If you read from dist while you’re writing it, an edge processed later in the same round can extend a path that was improved earlier in that round, so one round can add several edges. That’s harmless for classic Bellman-Ford (more progress per round is fine when there’s no cap). It’s wrong when rounds are the edge budget.
Classic Bellman-Ford: a shortest simple path has at most V − 1 edges, so V − 1 rounds (in place, no snapshot) handle any graph with negative edges but no negative cycle. If a V-th round still improves something, a negative cycle is reachable from the source.
Early exit: if a whole round changes nothing, later rounds would see the same inputs and change nothing either, so you can stop.
Worked example: 4 nodes, source 0, and we care about node 1.
Edges, in this list order: 0->2 (1), 2->3 (1), 3->1 (1), 0->1 (5), 2->1 (3).
The paths to node 1 are: 0->1 = 5 (1 edge), 0->2->1 = 1 + 3 = 4 (2 edges), and 0->2->3->1 = 1 + 1 + 1 = 3 (3 edges). The cheapest path overall uses 3 edges. With a budget of 2 edges the answer is 4, and with 1 edge it’s 5. Dijkstra would settle node 1 at 3 and couldn’t give you the 2-edge answer.
Diagram
The last row is the snapshot bug in action. With in-place updates and this edge order, round 1 already reports a 3-edge path.
Implementation
INF = float("inf")
def bounded_shortest(n, edges, src, max_edges):
# invariant: after round r, dist[v] = cheapest src -> v using at most r edges
dist = [INF] * n
dist[src] = 0
for r in range(1, max_edges + 1):
prev = dist[:] # round r-1's values: paths with <= r-1 edges
for u, v, w in edges:
# extend a <= r-1 edge path by exactly one edge; reading prev (not dist)
# stops 0->2, 2->3, 3->1 from chaining inside one round
# (recalled: INF + w stays INF, so unreachable u never improves v)
if prev[u] + w < dist[v]:
dist[v] = prev[u] + w
if dist == prev: # round r changed nothing: rounds r+1.. cannot either
break
return dist
edges = [(0, 2, 1), (2, 3, 1), (3, 1, 1), (0, 1, 5), (2, 1, 3)]
print([bounded_shortest(4, edges, 0, k)[1] for k in (1, 2, 3, 4)]) # [5, 4, 3, 3]
Edge cases I ran: max_edges = 0 leaves only the source at 0 ([0, inf, inf]), a single node gives [0], and a negative edge (0->1 (4), 1->2 (-3), 0->2 (2), budget 2) gives [0, 4, 1], which is correct because 4 − 3 = 1 beats the direct 2.
Complexity. k = the edge budget. O(k · E) time and O(V) space (two arrays). Classic Bellman-Ford is O(V · E).
Recognition
Signals: “at most k edges/stops/steps/transfers”, negative weights, “detect a negative cycle” or “arbitrage”. The cost of a path depends on both its total and its length.
It’s distinct from Dijkstra, which is faster with non-negative weights and no length cap but breaks with either. It’s also distinct from BFS over (node, edges-used) states, which is another way to handle a cap and costs O(k · (V + E)) in the worst case.
On the list, Cheapest Flights Within K Stops shows the “at most k” signal. How its stop limit maps onto a number of rounds is part of solving it.
Pitfalls
- In-place updates with an edge budget. You get the wrong answer (3 instead of 5 at budget 1).
- Off-by-one between the budget and rounds. Make sure you know whether your limit counts edges or intermediate nodes. They differ by one.
INFarithmetic. In Python,float('inf') + wis stillinf(recalled). If you use a large integer sentinel instead, checkprev[u] != INFexplicitly, orINF + (-3)will look like a real distance.- Early exit with
dist == previs safe only because each round’s values depend only on the previous round’s.
Active Recall
- In round 2,
dist[3]becomes 2. Which path is that, and why couldn’t round 1 find it? - With in-place updates, round 1 reports
dist[1] = 3. Would reordering the edge list fix it? - Why is negative-edge
0->1 (4),1->2 (-3),0->2 (2)handled correctly here but can break Dijkstra? - You run classic Bellman-Ford for V − 1 rounds, then one more round, and something still improves. What do you conclude, and why V − 1?
Answer out loud or on paper first.
Mini-task
Skipped. Cheapest Flights Within K Stops is the only list problem that uses this, and it requires deriving how its own stop limit becomes the round budget, so we cover that when we solve it directly.
Transfer test
You have exchange rates between currencies, and you want to know if some sequence of trades turns 1 unit into more than 1 unit. Would you use Bellman-Ford? Why?
Integration
How they connect to Advanced Graphs. All five modules share one loop: keep a frontier, pick the next thing, update its neighbours. What changes is what you pick and why that pick is safe:
| Algorithm | Frontier | Pick | Safe because |
|---|---|---|---|
| Dijkstra | min-heap by path total d + w |
smallest total | non-negative weights: nothing later is cheaper |
| Prim | min-heap by single edge w |
cheapest edge leaving the tree | cut property on (tree, rest) |
| Kruskal | all edges, sorted | cheapest edge between two components | cut property on (component, rest) |
| Kahn | queue of indegree-0 nodes | any ready node | all its prerequisites are already placed |
| Bellman-Ford | no frontier; every edge each round | nothing is final | round r covers every path of ≤ r edges |
The heap from Part 10 powers the first two, and Union-Find from Part 14 powers the third.
Distinguishing the competing approaches:
- Shortest path or spanning tree? Is there a source, and is the answer per node or per route? If yes, it’s a shortest path. Is the answer one total for connecting everything? Then it’s an MST. The example graph showed how the two differ: the shortest-path tree totalled 17 and the MST 11.
- Dijkstra or BFS? Equal weights mean BFS. Unequal non-negative weights mean Dijkstra.
- Dijkstra or Bellman-Ford? Negative weights, a cap on edges, or a negative-cycle question all mean Bellman-Ford (or BFS over (node, edges-used) states for the cap).
- Prim or Kruskal? Adjacency list or dense graph, go with Prim. Edge list, sparse graph, or you need the merge order by threshold, go with Kruskal.
- Kahn or DFS topo sort? Either works. Kahn when you need the cycle count, smallest-first order, or a uniqueness check. DFS when you’re already doing a DFS.
- Something none of these covers: “use every edge exactly once” is an Eulerian path, not a shortest path. The standard tool is Hierholzer’s algorithm (recalled: a DFS that consumes each edge once and records a node only after all its edges are used, then reverses the recording). It’s not taught here. Reconstruct Itinerary shows this signal.
Recognition checklist for an unfamiliar graph problem:
- What are the nodes and edges? Are they given, or hidden in a grid, a set of states, or a set of constraints? Directed or undirected?
- Is there a source? Is the answer per node, a single total, or an ordering?
- Are weights all equal, non-negative, or possibly negative?
- How is a path’s cost combined: sum, max of steps, count of edges? Does the “settle once” argument still hold for that rule?
- Is there a limit on path length (edges, stops, transfers)?
- Does every node need to be included (spanning), or every edge used once (Eulerian)?
- Are there order constraints? Which way does each arrow point, and could they contradict each other (a cycle)?
- What’s the size? Dense graphs change which version is fastest (O(V²) Prim, all-pairs methods for tiny V).
The problems
Work these with the solving cycle from Part 1: a 15-minute struggle, a one-sentence key insight, then spaced repetition. During the struggle, sketch a small example first and ask: DFS, BFS, Dijkstra, or topological sort? Do I need cycle detection, or just a visited set? Simulate by hand before coding, and be able to explain the traversal order and what stops an infinite loop.
6 problems · 0 easy · 3 medium · 3 hard · tracker spreadsheet (.xlsx)
| # | Problem | Difficulty | Coach |
|---|---|---|---|
| 1 | Network Delay Time | Medium | ChatGPT · Claude |
| 2 | Reconstruct Itinerary | Hard | ChatGPT · Claude |
| 3 | Min Cost to Connect All Points | Medium | ChatGPT · Claude |
| 4 | Swim In Rising Water | Hard | ChatGPT · Claude |
| 5 | Alien Dictionary | Hard | ChatGPT · Claude |
| 6 | Cheapest Flights Within K Stops | Medium | ChatGPT · Claude |
Take this lesson as a live session
To be taught this topic interactively, with the coach waiting for your answers at every checkpoint, open the full lesson prompt in a chat.