Free lesson · DSA Mastery - Interview Prep, End to End

Cheapest Flights Within K Stops

Hard11 min readdsagraphs

Cheapest Flights Within K Stops

Cheapest Flights Within K Stops adds a constraint that twists the shortest-path computation: find the cheapest price from a source to a destination using at most k stops (at most k + 1 edges). The stop limit means a plain Dijkstra's (which minimizes cost regardless of edge count) can give a wrong answer - a cheaper path might use too many stops. The clean technique is Bellman-Ford with bounded rounds: relax all edges exactly k + 1 times (each round extends paths by one edge), so after k + 1 rounds you have the cheapest path using at most k + 1 edges. Alternatively, Dijkstra's with an augmented state (city, stops used). It teaches handling an edge-count constraint on a shortest path - a key variant where Bellman-Ford's round structure shines and where state augmentation adapts Dijkstra's. We present Bellman-Ford bounded rounds (canonical) and augmented-state Dijkstra's (alternative).

The insight: the k-stop limit caps the number of edges in the path at k + 1. Bellman-Ford's structure fits perfectly: each relaxation round extends shortest paths by one more edge, so running exactly k + 1 rounds yields the cheapest paths using at most k + 1 edges - precisely the constraint. The crucial detail: each round must relax using distances from the previous round only (a snapshot), so a single round doesn't chain multiple edges. Plain Dijkstra's fails because it minimizes cost ignoring the edge count, possibly settling the destination via a too-long cheap path; the fix is either bounded Bellman-Ford or augmenting Dijkstra's state with stops used.

The Problem

There are n cities connected by some number of flights. You are given flights where flights[i] = [from_i, to_i, price_i] indicates a flight from city from_i to city to_i with cost price_i.

You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input:  n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],
        src = 0, dst = 3, k = 1
Output: 700

Explanation: With at most 1 stop, the route 0→1→3 costs 700. (0→1→2→3 costs 400 but uses 2 stops.)

Example 2:

Input:  n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200

Explanation: 0→1→2 (1 stop) costs 200, cheaper than the direct 0→2 (500).

Constraints:

• 1 <= n <= 100; 0 <= flights.length <= n * (n - 1) / 2
• flights[i].length == 3; 0 <= from_i, to_i < n; from_i != to_i; 1 <= price_i <= 10^4
• 0 <= src, dst, k < n; src != dst.

Approaches Overview

Bellman-Ford relaxes all edges k + 1 times, each round using a snapshot of the previous round's distances (so one round adds at most one edge). After k + 1 rounds, dist[dst] is the cheapest price using at most k + 1 edges (k stops), or -1 if unreachable. The augmented-state Dijkstra's tracks (city, stops used) as the state, exploring by cost but respecting the stop budget. Bellman-Ford's bounded-round structure is the cleanest fit for the edge-count constraint.

Approach 1: Bellman-Ford Bounded Rounds - Canonical

The Idea

Initialize dist[src] = 0, others infinity. Repeat k + 1 times: make a copy of the current dist (the snapshot), then relax every flight using the snapshot's distances - if snapshot[from] + price < dist[to], dist[to] = snapshot[from] + price. Using the snapshot ensures each round adds at most one edge to any path (no chaining within a round). After k + 1 rounds, dist[dst] is the cheapest at-most-k+1-edge price, or -1 if still infinity.

Logic Flowchart

graph TD
    A["dist[src]=0, others INF"] --> B["repeat k+1 times:"]
    B --> C["snapshot = copy of dist"]
    C --> D["for each flight (from, to, price): relax using snapshot[from]"]
    D --> E{"more rounds?"}
    E -->|Yes| B
    E -->|No| F{"dist[dst] == INF?"}
    F -->|Yes| G["return -1"]
    F -->|No| H["return dist[dst]"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Cheapest Flights by bounded Bellman-Ford. Over k plus one rounds, each using a snapshot of the previous distances, every flight is relaxed, giving the cheapest price within the stop limit.

Code

public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int round = 0; round <= k; round++) {         // k+1 rounds = at most k+1 edges
        int[] snapshot = dist.clone();                 // use previous round's distances only
        for (int[] f : flights) {
            int from = f[0], to = f[1], price = f[2];
            if (snapshot[from] != Integer.MAX_VALUE && snapshot[from] + price < dist[to])
                dist[to] = snapshot[from] + price;     // relax from snapshot (one edge added)
        }
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

// Usage:
// findCheapestPrice(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1) -> 700
// findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) -> 200

This Java code finds the cheapest price within k stops by bounded Bellman-Ford: over k plus one rounds, each relaxing every flight from a snapshot of the previous distances, ensuring each round adds at most one edge.

Step-by-Step Walkthrough

A frame-by-frame trace on Example 1, src=0, dst=3, k=1 (so 2 rounds):

graph LR
    F0["dist[0]=0, others INF. k=1 → 2 rounds"]
    F1["round 0: snapshot all-INF except 0. relax: dist[1]=100 (0→1). others stay"]
    F2["round 1: snapshot has dist[1]=100. relax: dist[2]=200 (1→2), dist[3]=700 (1→3, 100+600)"]
    F3["dist[3]=700 (route 0→1→3, 1 stop). 0→1→2→3=400 needs 2 stops, excluded → return 700"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough finds the cheapest within one stop: after two rounds, the route zero to one to three costs seven hundred, while the cheaper two-stop route is correctly excluded.

Result: 700.

Complexity

Time: O(k · E) - k + 1 rounds, each relaxing all edges. Space: O(V) for dist and the snapshot.

Approach 2: Augmented-State Dijkstra's - Alternative

The Idea

State is (city, stopsUsed). Min-heap keyed by cost. From src with 0 stops, explore: popping (city, cost, stops), if city == dst return cost; if stops <= k, push each neighbor with cost + price and stops + 1. Track the best cost per (city, stops) to prune. The stop budget is part of the state, so Dijkstra's respects it.

Code

public static int findCheapestPriceDijkstra(int n, int[][] flights, int src, int dst, int k) {
    List<int[]>[] adj = new List[n];
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    for (int[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // {city, cost, stops}
    pq.offer(new int[]{src, 0, 0});
    int[] minStops = new int[n];
    Arrays.fill(minStops, Integer.MAX_VALUE);

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int city = cur[0], cost = cur[1], stops = cur[2];
        if (city == dst) return cost;                  // first pop of dst = cheapest within budget
        if (stops > k || stops >= minStops[city]) continue;   // over budget or worse
        minStops[city] = stops;
        for (int[] nb : adj[city])
            pq.offer(new int[]{nb[0], cost + nb[1], stops + 1});
    }
    return -1;
}

// Usage: findCheapestPriceDijkstra(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) -> 200

This Java code finds the cheapest price within k stops by augmented-state Dijkstra's: the state tracks city and stops used, exploring by cost while respecting the stop budget.

Complexity

Time: O(E · k · log) - states multiplied by the stop dimension. Space: O(V · k).

Complexity Comparison

Bellman-Ford with k + 1 bounded rounds is the cleanest fit: the round structure naturally caps the edge count, and the snapshot ensures each round extends paths by exactly one edge. The augmented-state Dijkstra's adds the stop budget as a state dimension. Both respect the stop constraint that plain Dijkstra's would violate. Bellman-Ford is simpler and the canonical choice for edge-count-bounded shortest paths.

Variations & Follow-ups

Why does plain Dijkstra's fail, and why does the stop limit demand a different approach?

Plain Dijkstra's finds the cheapest path regardless of edge count - it settles each node at its globally cheapest distance, ignoring how many edges that path uses. But Cheapest Flights caps the path at k stops (k + 1 edges), and the cheapest path within that limit may differ from the cheapest path overall. Example 1 shows this starkly: the overall cheapest route 0→1→2→3 costs 400 but uses 2 stops; within the 1-stop limit, the best is 0→1→3 at 700. Plain Dijkstra's would settle node 3 at 400 (the cheaper, longer path), giving the wrong answer for the constrained problem. The issue is that Dijkstra's greedy "settle the cheapest" doesn't track how many edges a path used, so it can't enforce the stop limit. Worse, naively adding a stop check to Dijkstra's is subtle: a node might be reachable cheaply with many stops or expensively with few, and which is "better" depends on whether you have stops to spare - so the cheapest-cost-so-far isn't a sufficient state. The constraint fundamentally couples cost and edge count, requiring either Bellman-Ford's edge-bounded rounds or augmenting the state with stops used. This is the lesson: an edge-count (or stop) constraint on a shortest path breaks plain Dijkstra's, demanding a structure that tracks path length - the recurring theme of "when the standard algorithm's notion of 'best' is insufficient, augment the state or change the algorithm."

Why does Bellman-Ford's round structure perfectly fit the stop limit, and why the snapshot?

Bellman-Ford relaxes all edges in rounds, and a key property is that after r rounds, dist[v] is the shortest distance to v using at most r edges. Each round propagates distances one more edge outward. This exactly matches the stop constraint: at most k stops means at most k + 1 edges, so running exactly k + 1 rounds gives the cheapest path using at most k + 1 edges - the precise answer. The round structure naturally bounds the edge count, which is why Bellman-Ford is the elegant fit (plain Dijkstra's has no such per-edge-count notion). The snapshot is the critical correctness detail. Within a single round, if you relaxed using the currently-updating dist array, a path could chain multiple edges in one round (relax 0→1, then immediately use the new dist[1] to relax 1→2, adding two edges in one round) - violating the "one edge per round" property and overcounting how few stops a path uses. To prevent this, each round relaxes using a snapshot (a copy) of the previous round's dist, so updates within a round don't feed into each other - each round adds at most one edge to any path. This snapshot discipline is what makes the round count equal the edge-count bound. Forgetting the snapshot is the classic bug: it lets cheaper-but-longer paths leak in, breaking the stop limit. The snapshot ensures round r produces exactly "shortest with ≤ r edges," making k + 1 rounds give the constrained answer.

How does the augmented-state Dijkstra's alternative work, and why track (city, stops)?

The alternative adapts Dijkstra's by augmenting the state: instead of just city, the state is (city, stopsUsed). The min-heap is keyed by cost, but each heap entry carries the stop count, and you only expand a state if stops <= k. This works because the stop budget is now part of the state - reaching a city with 1 stop is a different state than reaching it with 3 stops, since they have different remaining budgets and thus different future options (echoing the augmented-state BFS from Shortest Path with Obstacles Elimination, where the state was (cell, eliminations used)). The same principle applies: when a resource consumed along the path (here, stops) affects feasibility, it must be in the state. The implementation explores by cost (Dijkstra's greedy) but respects the budget, and prunes states that reach a city with more stops than a previously-seen cheaper-or-equal route (since more stops used is never advantageous at equal-or-higher cost). The first time the destination is popped, that's the cheapest cost within budget. This augmented-state Dijkstra's and bounded Bellman-Ford are two valid expressions of the same idea - track the edge count alongside cost. Bellman-Ford does it implicitly (round = edge count); Dijkstra's does it explicitly (stops in the state). Bellman-Ford is simpler to code here (no augmented heap state, just rounds), which is why it's canonical, but the augmented-state approach generalizes the "add a dimension to the state when a constraint couples with the objective" technique seen throughout the graph module.

How does this generalize, and when do you reach for Bellman-Ford vs. augmented Dijkstra's?

The broad lesson: a constraint on the number of edges (or any resource consumed per edge) in a shortest path requires tracking that resource, either via Bellman-Ford's bounded rounds or Dijkstra's augmented state. This pattern recurs: shortest path with at most k edges (Bellman-Ford k rounds), cheapest path with a fuel/time/budget limit (augment state with the resource), shortest path visiting exactly m intermediate nodes, etc. The decision between approaches: Bellman-Ford bounded rounds is cleanest when the constraint is purely an edge-count limit and weights are arbitrary (even negative) - its round structure directly bounds edges, and it's simple (O(k·E), just an array and a snapshot). Augmented-state Dijkstra's is preferable when weights are non-negative and the resource constraint is more complex than a simple edge count (a continuous budget, multiple resources), where Dijkstra's cost-ordered exploration prunes more effectively - but it pays the cost of a larger state space (O(V · k) states). For Cheapest Flights specifically, the constraint is a clean stop count, so Bellman-Ford's k + 1 rounds are the elegant, canonical solution. Recognizing "this shortest-path problem has a resource/edge-count constraint coupled with the cost objective" - and knowing both the Bellman-Ford-rounds and augmented-state-Dijkstra's responses - is the transferable skill. It connects the shortest-path algorithms to the state-augmentation technique from BFS, showing that constrained shortest paths need the path's resource usage tracked, whichever algorithm carries it.

What about edge cases?

• No route within k stops: dist[dst] stays infinity → -1.
• Direct flight cheaper or only option (Example 2 reversed): The 0-stop direct flight is considered in round 0.
• k = 0 (no stops, direct only): One round; only direct flights from src count.
• Cheaper path exceeds the stop limit (Example 1): Excluded; the within-budget answer is returned.
• k ≥ n − 1 (no effective limit): Reduces to ordinary shortest path (enough rounds for any simple path).

Common Interview Pitfalls

• Using plain Dijkstra's. It ignores the stop count and can return a too-long cheap path; use bounded Bellman-Ford or augmented state.
• Forgetting the snapshot in Bellman-Ford. Relaxing from the live array chains multiple edges per round, breaking the stop bound.
• Off-by-one in rounds. k stops = k + 1 edges = k + 1 rounds; loop round from 0 to k inclusive.
• Not handling the unreachable case. Return -1 if the destination's distance stays infinity.

Why This Topic Matters

Cheapest Flights Within K Stops adds an edge-count constraint that breaks plain Dijkstra's (which ignores path length). The clean fix is bounded Bellman-Ford: k + 1 rounds, each relaxing all edges from a snapshot of the previous round, so each round adds exactly one edge - yielding the cheapest path within k + 1 edges. The alternative augments Dijkstra's state with stops used. It teaches that a resource/edge-count constraint coupled with the cost objective must be tracked - via Bellman-Ford's rounds or state augmentation - connecting shortest paths to the state-augmentation technique.

The next topic, Path with Maximum Probability, twists the cost-combining rule: edges carry success probabilities (between 0 and 1), the probability of a path is the product of its edge probabilities, and you want the path from source to target with maximum probability. Instead of minimizing a sum of weights, you maximize a product of probabilities - solved by a modified Dijkstra's using a max-heap (expand the highest-probability node first) and multiplying probabilities during relaxation. It teaches adapting Dijkstra's to a different cost algebra: max instead of min, product instead of sum, while the greedy priority-queue structure (always expand the best frontier) stays intact - reinforcing that Dijkstra's is a template parameterized by its cost-combining and comparison operations.

Back to DSA Mastery - Interview Prep, End to End