☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Cheapest flight within K stops

Hard TUF ID 519 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

There are n cities numbered 0 to n - 1 and a list of one-way flights, each written as [from, to, price]. Given a source city src, a destination dst and an integer k, return the cheapest total price of a trip from src to dst that makes at most k stops, or -1 if no such trip exists. A stop is an intermediate city, so k stops means at most k + 1 flights.

Constraints (LeetCode 787): 1 ≤ n ≤ 100, every price is between 1 and 10^4, there are no duplicate flights, 0 ≤ k < n and src != dst.

Example 1

n = 4, flights = [[0,1,100], [1,2,100], [2,0,100], [1,3,600], [2,3,200]]
src = 0, dst = 3, k = 1
answer = 700        // 0 -> 1 -> 3; the cheaper 0 -> 1 -> 2 -> 3 (400) needs 2 stops

Example 2

n = 3, flights = [[0,1,100], [1,2,100], [0,2,500]], src = 0, dst = 2, k = 0
answer = 500        // no stops allowed, so only the direct flight counts

The stop limit is what makes this problem different from an ordinary shortest path. The cheapest route overall may be useless because it is too long, so the algorithm has to remember not just “how cheaply can I reach this city” but “how cheaply can I reach it with this many flights”.

Approach 1: Brute force

Intuition. Try every route that uses at most k + 1 flights. From the current city, branch on every outgoing flight and recurse with one flight fewer in the budget. The budget strictly shrinks, so the recursion terminates even when the flight graph has cycles. Because prices are positive, once we land in dst there is no point flying on: any continuation that returns to dst costs more.

Algorithm.

  1. Build an adjacency list city -> list of {to, price}.
  2. cheapestFrom(node, flightsLeft) returns 0 if node == dst, infinity if flightsLeft == 0, and otherwise the minimum over flights node -> next of price + cheapestFrom(next, flightsLeft - 1).
  3. Call it with (src, k + 1) and turn infinity into -1.
static int bruteForce(int n, int[][] flights, int src, int dst, int k) {
    List<List<int[]>> adj = buildGraph(n, flights);
    long best = cheapestFrom(adj, src, dst, k + 1);
    return best == Long.MAX_VALUE ? -1 : (int) best;
}

static long cheapestFrom(List<List<int[]>> adj, int node, int dst, int flightsLeft) {
    if (node == dst) return 0;                       // prices are positive, so going on never helps
    if (flightsLeft == 0) return Long.MAX_VALUE;
    long best = Long.MAX_VALUE;
    for (int[] e : adj.get(node)) {
        long rest = cheapestFrom(adj, e[0], dst, flightsLeft - 1);
        if (rest != Long.MAX_VALUE) best = Math.min(best, e[1] + rest);
    }
    return best;
}

Complexity. Time O(d^(k+1)) where d is the largest number of outgoing flights from a city, because every route of up to k + 1 flights is explored; with n = 100 and k = 99 that is astronomically large. Space O(n + E) for the graph and O(k) for the recursion stack.

The recursion revisits the same (city, flightsLeft) pair over and over. Both faster approaches avoid that by treating the pair, rather than the city alone, as the real state.

Approach 2: Better, BFS layered by stops

Intuition. The natural first idea is Dijkstra on price, but it gives wrong answers here. Dijkstra keeps one best price per city and throws away any later, more expensive arrival. In this problem the more expensive arrival may be the one that used fewer flights, and only it can still be extended. Take flights 0→1 (1), 1→2 (1), 2→3 (1), 0→2 (5) with k = 1. Dijkstra settles city 2 at price 2 (two flights), discards the arrival at price 5 (one flight), and then cannot reach 3 without a third flight. The correct answer is 6 via 0 → 2 → 3.

The fix is to explore in order of stops instead of price. Put states {stops, city, cost} into a plain FIFO queue. Each push adds exactly one flight, so every state with s stops leaves the queue before any state with s + 1. Keep dist[city] as the cheapest price seen so far for that city, and push a new state only when it lowers dist[next].

Why is that pruning safe? Suppose we try to reach next with cost c and find dist[next] ≤ c. That record was created by a state with at most as many flights as ours, because the queue has not yet produced anything with more stops. That earlier state is no more expensive and no longer, so anything our state could do later, it can do at least as well. Note also that a popped state expands using its own cost, not dist[node], because dist[node] may since have been lowered by a longer route that cannot afford the extra flights.

Algorithm.

  1. dist[src] = 0, all others infinity. Push {0, src, 0}.
  2. Pop {stops, node, cost}. If stops > k, skip it: one more flight would exceed the limit.
  3. For each flight node -> next with price: if cost + price < dist[next], set dist[next] and push {stops + 1, next, cost + price}.
  4. When the queue empties, return dist[dst] or -1.
static int bfsByStops(int n, int[][] flights, int src, int dst, int k) {
    List<List<int[]>> adj = buildGraph(n, flights);
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Deque<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{0, src, 0});               // {stops, node, cost}
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int stops = cur[0], node = cur[1], cost = cur[2];
        if (stops > k) continue;                     // one more flight would exceed k stops
        for (int[] e : adj.get(node)) {
            int next = e[0], price = e[1];
            if (cost + price < dist[next]) {
                dist[next] = cost + price;
                queue.offer(new int[]{stops + 1, next, cost + price});
            }
        }
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

Dry run on the trap example (k = 1, dst = 3):

popped stops ok? relaxations queue after
{0, 0, 0} yes dist[1] = 1, dist[2] = 5 {1,1,1}, {1,2,5}
{1, 1, 1} yes dist[2] = 2 {1,2,5}, {2,2,2}
{1, 2, 5} yes dist[3] = 6 {2,2,2}, {2,3,6}
{2, 2, 2} no (2 > 1) none {2,3,6}
{2, 3, 6} no none empty

The state {1, 2, 5} is expanded with cost 5 even though dist[2] is already 2. That is exactly the arrival plain Dijkstra would have thrown away.

Complexity. Each state relaxes its city’s outgoing flights, states are created only when they strictly lower a dist value, and nothing past level k + 1 is expanded. In practice this runs in about O(k · E) time. The bound is not tight in theory, because a city can be improved several times within one level and is then expanded several times. Space O(n + E) for the graph plus the queue.

Approach 3: Optimal, Bellman-Ford with k + 1 rounds

Intuition. Bellman-Ford relaxes every edge once per round. Its invariant is that after r rounds, dist[v] is no more than the cheapest route to v that uses at most r edges. Normally a round can do better than that: if edge u → v is relaxed after dist[u] was lowered in the same round, a route can grow by several edges in one round. For ordinary shortest paths that is a harmless speed-up, but here it would silently break the flight limit.

So each round reads from the previous round’s array and writes into a copy. Then after round r (counting from 0), dist[v] is exactly the cheapest price using at most r + 1 flights. Running k + 1 rounds answers the question.

Algorithm.

  1. dist[src] = 0, all others infinity.
  2. Repeat k + 1 times: next = copy of dist; for every flight u -> v, if dist[u] is finite and dist[u] + price < next[v], set next[v]. Then dist = next.
  3. Return dist[dst] or -1.
static int bellmanFordKRounds(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++) {       // after round r, dist uses at most r + 1 flights
        int[] next = dist.clone();
        for (int[] f : flights) {
            int u = f[0], v = f[1], price = f[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + price < next[v]) next[v] = dist[u] + price;
        }
        dist = next;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

Dry run on Example 1 (k = 1, so two rounds):

round reads writes dist after
start     [0, ∞, ∞, ∞]
0 (1 flight) dist[0] = 0 next[1] = 100 [0, 100, ∞, ∞]
1 (2 flights) dist[1] = 100 next[2] = 200, next[3] = 700 [0, 100, 200, 700]

In round 1 the flight 2 → 3 reads the old dist[2] = ∞, so it does nothing. Had we updated in place, it would have read the fresh 200 and produced 400, a three-flight route that k = 1 does not allow.

Complexity. Time O(k · (n + E)): k + 1 rounds, each copying n values and scanning every flight once. Space O(n) for two distance arrays. The bound is guaranteed regardless of graph shape, which is why this is the version to reach for when you need a predictable worst case.

Edge cases and pitfalls