p64 — Cheapest Flights Within K Stops

Source: LeetCode 787 · Medium · Topics: Graph, Bellman-Ford, BFS-with-state, DP Companies (2024–2025): Amazon (high), Meta (high), Microsoft (medium-high), Google (medium) Loop position: Why Dijkstra fails when you constrain path length. The constraint “≤ K stops” breaks Dijkstra’s correctness — you must use Bellman-Ford (K+1 relaxations) or BFS-with-(node, stops) state. Tests algorithm-selection judgment, not just implementation.

1. Quick Context

n cities, flights[i] = [from, to, price]. Find cheapest price from src to dst using ≤ K stops. Return -1 if impossible.

“K stops” = at most K+1 edges (a direct flight is 0 stops = 1 edge).

Bellman-Ford bounded by K+1 relaxations:
prev = [INF] * n; prev[src] = 0
for _ in range(K + 1):
    curr = prev.copy()
    for u, v, w in flights:
        if prev[u] + w < curr[v]:
            curr[v] = prev[u] + w
    prev = curr
return prev[dst] if prev[dst] != INF else -1

O(K · E) time, O(V) space.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/cheapest-flights-within-k-stops/

STOP. 30-min timer. The Dijkstra-doesn’t-work insight is the hardest part.

3. Prerequisite Concepts

  • Dijkstra (p63) and its correctness conditions.
  • Bellman-Ford as iterative edge relaxation.
  • BFS-with-state (extended graph: (node, stops_used) pairs).
  • Path-length constraints and how they break greedy approaches.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Cheapest path with at most K+1 edges. Standard cheapest path EXCEPT for the length cap.

2. Clarify: Edges have weights ≥ 0? (Yes.) “K stops” = K intermediate cities = K+1 edges. Verify with interviewer.

3. Examples:

  • n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, K=1 → 200 (0→1→2 uses 1 stop).
  • Same with K=0 → 500 (direct only).

5. Brute force: DFS with depth limit K+1; exponential in depth.

6. Target: O(K · E).

7. Pattern: Bellman-Ford bounded relaxation, OR BFS-with-state.

8. Develop: see solution.py.

9. Test: K=0 (direct only); K=n (effectively unbounded); unreachable; multi-edge same pair.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why Dijkstra FAILS here

Dijkstra greedily finalizes the cheapest unfinished node. With a stops-constraint, the “cheapest reachable so far” may have used too many stops to be extensible, while a more expensive path with fewer stops remains better for downstream extensions.

Counterexample:

0 → 1 (1)
0 → 2 (5)
1 → 2 (1)
2 → 3 (1)
K = 1, src=0, dst=3

From 0, Dijkstra explores: dist[1]=1, dist[2]=2 (via 0→1→2), dist[3]=3 (via 0→1→2→3). But 0→1→2→3 uses 2 stops — exceeds K=1. The correct answer is 0→2→3 = 6 (1 stop).

Dijkstra needs augmentation: track (node, stops_used) as the state, OR switch to Bellman-Ford.

6.2 Bellman-Ford with K+1 iterations — why it’s correct

Bellman-Ford’s invariant after iteration i: dist[v] = cheapest cost reaching v using ≤ i edges. Run exactly K+1 iterations; dist[dst] = cheapest with ≤ K+1 edges = ≤ K stops. Done.

Critical: use prev and curr arrays separately. If you relax in-place with a single array, you can chain multiple relaxations in one iteration — each “iteration” then represents using ≤ many edges, not exactly one more. Wrong answer.

for _ in range(K + 1):
    curr = prev.copy()
    for u, v, w in flights:
        curr[v] = min(curr[v], prev[u] + w)
    prev = curr

The prev.copy() is THE detail. Skipping it is the most common interview bug.

6.3 BFS-with-state alternative

Extend the state space: each state is (node, stops_used). Run BFS / modified Dijkstra over states. Transitions from (u, k): for each outgoing edge (u, v, w), go to (v, k+1) with added cost w, allowed if k+1 ≤ K+1.

Heap-based Dijkstra on this extended graph works correctly because the augmented state has no constraint that breaks the cut property.

Time: O((V·K + E) log (V·K)) — usually slower than Bellman-Ford for this problem unless K is small relative to V.

6.4 SPFA / Modified Bellman-Ford

You can speed up Bellman-Ford with SPFA (Shortest Path Faster Algorithm) — a queue-based relaxation that only revisits updated nodes. Same K-iteration bound. In practice often faster than plain BF.

6.5 Why the constraint changes everything

Adding a “≤ K edges” constraint converts the SSSP from a cut-property problem to a layered one. The DP is over layers (= edge counts), not over distances. This is a general lesson: path-constraint shortest path = layered DP, NOT cut-based greedy. Other instances: “exactly K edges” (uses powers of adjacency matrices), “at most K colors used,” “bounded resource consumption.”

6.6 Equivalent formulations

  • DP over edges: dp[k][v] = min cost to reach v using ≤ k edges. Bellman-Ford is this DP rolled to 1D.
  • Min-plus matrix power: A^k[i][j] (in min-plus semiring) = min cost using exactly k edges. Sum over k ≤ K+1. Matrix exponentiation gives O(V³ log K) — useful when K is huge.

6.7 Subtleties

  • K=0: direct flights only. Common edge case bug.
  • Self-loops or multi-edges: must keep them all in the adjacency / edge list; Bellman-Ford handles correctly.
  • Cycle in graph: doesn’t matter; the K-iteration cap prevents infinite traversal.

7. Anti-Pattern Analysis

  1. Use Dijkstra naively — silently wrong on stops-constrained paths.
  2. Bellman-Ford in-place (no prev.copy()) — chains relaxations within one iteration; counts wrong number of stops.
  3. Off-by-one on K: “K stops” = “K+1 edges.” Confuse and you compute the wrong path-length cap.
  4. Heap-based Dijkstra over (node, cost) with visited-set — visited-set prevents revisiting nodes via cheaper-stops paths; wrong.
  5. Track stops without state — single dist[v] array can’t disambiguate paths with same cost different stops.
  6. DFS without memoization — exponential blowup; on LC times out.

8. Skills & Takeaways

  • Recognize when a constraint breaks Dijkstra’s correctness.
  • Bellman-Ford as bounded-edge-count DP.
  • BFS-with-state for augmented graphs.
  • The “prev vs curr” array discipline in iterative DP.
  • General pattern: constraint on path = extra DP dimension.

9. When to Move On

  • Solve LC 787 cold in 18 min with both Bellman-Ford and BFS-with-state.
  • Articulate why Dijkstra fails in 60 seconds with the explicit counterexample.
  • Solve LC 743 (Dijkstra, p63) and LC 787 back-to-back, switching algorithms appropriately.
  • Solve LC 1928 (Min Cost to Reach Destination In Time) — another layered DP.

10. Company Context

  • Amazon: L6 onsite; productized as “warehouse-to-warehouse with hop limit.”
  • Meta: E5; expects clean Bellman-Ford with prev.copy().
  • Microsoft: L65+; Azure Front Door routing with hop limit.
  • Google: L5; less common but appears as the airline-pricing variant.
  • Uber: L5; multi-modal hop-bounded routing.

Scorecard for strong: “Recognized Dijkstra fails; chose Bellman-Ford; correctly used prev/curr arrays; articulated K=K+1-edges; mentioned BFS-with-state alternative.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Algorithm choiceDijkstra (wrong)“BFS” vagueBellman-Ford justified+ BFS-with-state alternative + tradeoff
Prev/curr disciplineBugAfter promptCold+ explains why in-place fails
K semanticsConfusedCorrect after exampleK=K+1 edges cold+ connects to general layered-DP pattern
CounterexampleNoneSketchesConstructs+ generalizes to broader class

12. Level Delta

  • Mid (L4): Bellman-Ford with K+1 iterations, prev/curr arrays.
  • Senior (L5): + BFS-with-state via heapq on (cost, node, stops) + counterexample for Dijkstra.
  • Staff (L6): + min-plus matrix exponentiation for huge K + SPFA optimization + general “constraint = extra DP dimension” pattern.
  • Principal (L7+): + LP relaxation framing + resource-constrained shortest path NP-hardness for arbitrary resources + production airline-pricing systems (multi-fare-class with bag/seat constraints).

13. Follow-up Q&A

Q1: K is huge (say, 10^9). A1: Bellman-Ford is O(K·E) — too slow. Use min-plus matrix exponentiation: O(V³ log K). Or observe: if K ≥ V-1, you’re effectively running unbounded shortest path (use Dijkstra).

Q2: Allow negative weights. A2: Bellman-Ford still works (it natively handles negatives). Dijkstra would already fail. Detect negative cycles by running one extra iteration; any further improvement indicates a negative cycle.

Q3: Reconstruct the actual flight sequence. A3: Maintain parent[k][v] during Bellman-Ford (the predecessor on the iteration when v’s distance improved). Walk back.

Q4: Multiple sources, single destination. A4: Add a “super-source” with 0-cost edges to all real sources; run Bellman-Ford from super-source.

Q5: Why does prev.copy() matter? A5: Without it, in-place updates can cascade: relaxing dist[v] then immediately using new dist[v] to relax dist[w] chains TWO edges in one iteration, blowing the K-edge cap.

14. Solution Walkthrough

See solution.py:

  • find_cheapest_price_bf — Bellman-Ford with prev/curr, K+1 iterations.
  • find_cheapest_price_bfs — Dijkstra over (cost, node, stops_used) states.
  • find_cheapest_price_brute — DFS with depth-limit K+1, exhaustive.

15. Beyond the Problem

Principal code review: “This is the problem that teaches you when to STOP reaching for Dijkstra. Every time someone proposes a path-finding problem with an extra constraint — ‘at most K hops,’ ‘within budget B,’ ‘using at most M road segments’ — the same lesson applies: the constraint creates a new DP dimension, and greedy algorithms that rely on cut properties break. The fix is one of three patterns: Bellman-Ford with bounded iterations, augmented state in BFS/Dijkstra, or LP relaxation when the constraints are linear. In airline-pricing systems at scale, fares, bag rules, fare classes, layover lengths, and bilateral agreements all add dimensions; the production solver is a fully integer-programming engine, not a graph algorithm at all. Knowing where the line is — when Dijkstra suffices vs when you need bigger machinery — is what separates a coder from a path-planning engineer.”