Lab 05 — Bellman-Ford (Cheapest Flights Within K Stops)

Goal

Implement Bellman-Ford for shortest path on a graph that may contain negative weights, and exploit its iteration structure to solve the canonical “shortest path with at most K edges” problem. After this lab you should be able to recognize the K-edge-budget signal in <60 seconds, write Bellman-Ford from a blank slate in <10 minutes, and articulate the negative-cycle detection extension cleanly.

Background Concepts

Bellman-Ford runs V - 1 rounds; in each round, relax all E edges. After round i, dist[v] equals the shortest path from source to v using at most i edges. This invariant is the key insight for “K-edge-budget” problems: run the algorithm for K rounds (or K + 1, depending on edge-vs-stop semantics) and read off the answer. A V-th round that still relaxes any edge proves a negative cycle reachable from the source.

The complexity is O(V · E). It tolerates negative weights (unlike Dijkstra) but is slower on graphs without them. The “shortest path with at most K edges” framing is the most common interview reason to use Bellman-Ford.

Interview Context

Cheapest Flights Within K Stops (LC 787) is asked at Amazon, Bloomberg, and Adobe. The trap is candidates reaching for Dijkstra and being unable to bound edge count. The strong answer: “this is Bellman-Ford with K + 1 iterations, where K stops means K + 1 edges, complexity O(K · E).” That single sentence wins the round. Negative-cycle detection (e.g., currency arbitrage) is rarer at L4-L5 but standard at staff and on competitive programming exercises.

Problem Statement

You are given n cities and a list flights[i] = (from, to, price) of directed flights. Return the cheapest price from src to dst using at most K stops (i.e., K intermediate cities, K + 1 edges). Return -1 if no such route exists.

Constraints

  • 1 ≤ n ≤ 100; 0 ≤ |flights| ≤ n · (n − 1) / 2
  • 1 ≤ price ≤ 10^4
  • 0 ≤ src, dst, K < n; src ≠ dst

Clarifying Questions

  1. “K stops” — does this mean K intermediate cities (so K + 1 edges) or K edges total? (Per LC 787 statement: K stops = K intermediate = K + 1 edges.)
  2. Are prices positive? (Yes; no negative-cycle concerns here.)
  3. Are duplicate flights allowed? (Possible; pick min on relaxation.)
  4. Should we count src and dst as “stops”? (No — those are endpoints.)
  5. Is K = 0 allowed (direct flight only)? (Yes — 0 ≤ K.)

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)

n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, K=0
→ 500  (only direct allowed)

Initial Brute Force

DFS from src exploring all paths up to K + 1 edges; track minimum cost. Time exponential — O(V^(K+1)) — at K = 99, V = 100: infeasible.

Brute Force Complexity

O(V^(K+1)) — TLE for K > ~10.

Optimization Path

Bellman-Ford with K + 1 iterations: O((K + 1) · E). At K = 99, E ~ 5000: 5 × 10^5 ops — fast. The key technique: keep two distance arrays, prev and curr. In each iteration, compute curr[v] = min(prev[u] + w_uv) over all edges. Using prev (last round’s snapshot) prevents using more than one edge per round.

Modified Dijkstra with state (node, edges_used) also works: push (cost, node, edges_remaining) to a heap, expand only if edges_remaining > 0. Slightly slower than Bellman-Ford for this problem because the heap doesn’t prune effectively; both are correct.

Final Expected Approach

prev[i] = ∞ for all i; prev[src] = 0
for round in 1 .. 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] != ∞ else -1

The curr = prev.copy() ensures each round uses only edges from the previous round’s distances — bounding the path to at most one new edge per round.

Data Structures Used

  • Two arrays of size n: prev and curr.
  • The flight list as the edge list (no need to build adjacency).

Correctness Argument

Invariant: after round i, prev[v] = shortest path from src to v using at most i edges. Proof by induction. Base (i = 0): only src has prev = 0, all others ∞. Inductive step: any shortest i-edge path is either an (i-1)-edge path (already in prev[v]) or extends some (i-1)-edge path to u with edge (u, v); the inner loop catches the latter via prev[u] + w_uv → curr[v]. After K + 1 rounds, prev[dst] is the shortest at-most-K+1-edge path.

Why two arrays: without the copy, in-place updates could chain multiple edges in one round, breaking the at-most-i-edges invariant.

Complexity

OperationTimeSpace
Whole algorithmO((K + 1) · E)O(V)

Implementation Requirements

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        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

Tests

  • Standard: 0 → 1 → 2 with K=1 → 200; K=0 → 500.
  • No path: disconnected → -1.
  • Direct flight only: K=0, no direct → -1.
  • K very large (≥ V - 1): equivalent to unrestricted Bellman-Ford.
  • Tie: two K-stop paths with same cost — return the cost.
  • Stress: V=100 dense, K=99 random — verify against modified Dijkstra.

Follow-up Questions

  1. “Negative weights? Negative cycles?” → Run V rounds (not K); if round V relaxes any edge, negative cycle reachable from src exists.
  2. “All-pairs shortest path with negative weights, no cycles.” → Johnson’s algorithm: Bellman-Ford to reweight, then Dijkstra from each source.
  3. “Currency arbitrage detection.” → Build graph with weight = -log(rate); negative cycle = profitable arbitrage.
  4. “K is up to 10^9.” → Matrix exponentiation on the (min, +) semiring; O(V³ log K).
  5. “Online updates: new flights added live.” → Difficult. Restart Bellman-Ford on each query; or maintain incrementally with limited optimizations.

Product Extension

Travel-search engines (Kayak, Google Flights, Hipmunk) treat flight networks as graphs and apply variants of K-stop shortest path. The “fewest connections” filter is exactly K-stop. The “cheapest with up to 2 stops” is K=2 Bellman-Ford. Currency-arbitrage bots run Bellman-Ford continuously on FX-rate graphs to detect profit cycles in milliseconds.

Language/Runtime Follow-ups

  • Python: prev[:] is O(V) and acceptable. array.array('d', ...) for floats can speed up cache locality.
  • Java: int[] prev = new int[n]; Arrays.fill(prev, Integer.MAX_VALUE); Watch overflow when summing — use long if weights × edges can overflow int.
  • Go: prev := make([]int, n) with manual init to a large constant; copy(curr, prev) for the snapshot. Builtin math.MaxInt32 is fine.
  • C++: vector<int> prev(n, INT_MAX); Use long long if weights are large. std::copy for the snapshot.
  • JS/TS: Array.from({length: n}, () => Infinity) and prev.slice() for copy.

Common Bugs

  1. In-place updates without the prev/curr split — chains multiple edges per round, gives wrong answers.
  2. Running K rounds instead of K + 1 — off by one (K stops = K + 1 edges).
  3. Treating “K stops” as K edges — read carefully; LC 787 means K + 1 edges.
  4. Forgetting to copy prev to curr at the start of each round — uses stale curr from previous iteration.
  5. Returning prev[dst] without the unreachable check; INF leaks into output.
  6. Integer overflow on prev[u] + w when prev[u] is set to INT_MAX — guard with the unreachable check first.
  7. Confusing “K = 0 means direct only” with “K = 0 means src only”.

Debugging Strategy

For a small case, print prev at the end of each round. Verify that round 1 has dist[v] = w(src → v) for direct neighbors only; round 2 has 2-edge paths, etc. If the answer is wrong, compare with a brute-force enumeration of paths up to K + 1 edges. For negative-cycle problems, verify that round V actually relaxes an edge by tracking a “changed” flag.

Mastery Criteria

  • Recognized “shortest path with at most K edges” as Bellman-Ford in <60 seconds.
  • Articulated the iteration-as-edge-budget invariant unprompted.
  • Wrote Bellman-Ford from blank screen with prev/curr split in <10 minutes.
  • Stated O((K + 1) · E) complexity unprompted.
  • Solved LC 787 in <20 minutes from cold start.
  • Articulated negative-cycle detection in <30 seconds when asked.
  • Articulated when Dijkstra is preferable (no edge budget, non-negative weights) in <30 seconds.