Bellman–Ford with k rounds
Relax every edge k+1 times from a copy of the previous round.
After round i, dist[v] is the cheapest path using ≤ i edges.
01The intuition
Start with what you would do by hand
Four cities. Flights: 0 → 1 costs 100, 1 → 2 costs 100, 2 → 0 costs 100, 1 → 3 costs 600, 2 → 3 costs 200. You want the cheapest way from 0 to 3 with at most 1 stop, that is, at most 2 flights. By hand: 0 → 1 → 3 costs 700 and uses 2 flights. 0 → 1 → 2 → 3 costs 400 but uses 3 flights, too many. So the answer is 700.
Notice that the cheapest route overall is not allowed. Dijkstra would settle city 2 at 200 and then happily reach 3 for 400, ignoring the stop limit. We need a method where the number of flights is part of the bookkeeping.
Build the structure, one piece at a time
Piece one: a table dist[] of the cheapest cost found so far to each city, starting as {0: 0, 1: ∞, 2: ∞, 3: ∞}.
Piece two: the idea of a round. In one round, go through every flight once and relax it: if dist[u] + price < dist[v], set dist[v] to the smaller value. After one round, every city reachable with one flight has its correct 1-flight cost.
Piece three, the rule that enforces the limit: in each round, read from a copy of the previous round's table and write into a fresh one. Otherwise an update made early in the round could be reused later in the same round, letting a path grow by two flights in one round.
Run it. Round 1 (reads {0, ∞, ∞, ∞}): 0 → 1 gives 100; every other flight starts from an ∞ city and does nothing. Table after round 1: {0, 100, ∞, ∞}. Round 2 (reads that copy): 1 → 2 gives 200, 1 → 3 gives 700, 2 → 3 reads the copy's ∞ for city 2 and does nothing. Table after round 2: {0, 100, 200, 700}. With k = 1 stop we run k + 1 = 2 rounds and stop. dist[3] = 700.
Why it is correct
The invariant: after round i, dist[v] is the cheapest cost of any route to v that uses at most i flights. It holds for i = 0. If it holds after round i, then the cheapest route with at most i + 1 flights is either a route with at most i flights (already in the copy) or a route with at most i flights to some u followed by one flight u → v, and round i + 1 tries exactly that for every flight. Reading from the copy guarantees the "at most i flights to u" part was not padded during the current round.
This also handles negative prices, which Dijkstra cannot: nothing in the argument assumed a price is positive.
Why it is fast
Each round touches every flight once, and there are k + 1 rounds:
work = (k + 1) · E
For 100 cities, 5,000 flights and k = 3 that is 20,000 relaxations. Without the limit, the classic Bellman–Ford runs V − 1 rounds for the same reason: no shortest path uses more than V − 1 edges.
How to recognise it in an interview
Cues: "at most k stops", "within k edges", "negative weights", "cheapest route with a limit on legs". The first thing to say: "the limit is on edges, so I run k + 1 relaxation rounds from a copy of the previous table." Cheapest Flights Within K Stops is this exact routine. Network Delay Time has no limit, so Dijkstra is the better fit there; mention Bellman–Ford only if the interviewer adds negative times.
02The idea in one line
Relax every edge k+1 times from a copy of the previous round.
Reach for it when: Cheapest flights within k stops, negative edges, bounded-edge paths.
Cost: O(k · E) time.
03The walk-through, step by step
The video works one example: Cheapest Flights with k=1 on 4 cities. These are its captions in order, so you can follow without the video or check a step you missed.
- dist[0] = 0, others ∞. Each round allows one more edge
- Round 1: relax every edge using a copy of last round's values
- 0→1: 0 + 100 = 100 improves dist[1]
- 1→2: ∞ + 100 does not beat ∞, skip
- 2→0: ∞ + 100 does not beat 0, skip
- 1→3: ∞ + 600 does not beat ∞, skip
- 2→3: ∞ + 200 does not beat ∞, skip
- Round 2: relax every edge using a copy of last round's values
- 0→1: 0 + 100 does not beat 100, skip
- 1→2: 100 + 100 = 200 improves dist[2]
- 2→0: ∞ + 100 does not beat 0, skip
- 1→3: 100 + 600 = 700 improves dist[3]
- 2→3: ∞ + 200 does not beat 700, skip
- After k+1 = 2 rounds, dist[3] = 700 via 0→1→3 (0→1→2→3 needs 2 stops)
- k+1 rounds over all edges: O(k · E)
04Asked at Google
3 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Network Delay Time | Medium | 38 | last 6 months |
| Cheapest Flights Within K Stops | Medium | 36 | last 6 months |
| Minimum Cost to Reach Destination in Time | Hard | 8 |
05Related patterns
Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).