Cheapest Flights Within K Stops

You want to fly from one city to another. Direct flights are pricey. Connecting flights are cheaper, but each stop costs you time. So the airline lets you take at most a fixed number of stops. You want the cheapest trip inside that limit. This is a shortest path problem with a twist. The stop limit is what makes it interesting in interviews.

🎯 The Problem

You want the cheapest trip with a limit on stops. Here are the rules.

• You get n cities numbered 0 to n - 1.
• You get a list of flights. Each flight is [from, to, price], a one-way hop with a cost.
• You get a source src, a destination dst, and a number k.
• Find the cheapest price from src to dst using at most k stops in between.
• A stop is a city you pass through, not counting the start or the end.
• So k stops means up to k + 1 flights.
• If no trip fits the limit, return -1.

Let us keep the example simple. We fly from city 0 to city 2 with at most one stop. So we may take up to two flights.

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

Explanation: The route 0 -> 1 -> 2 costs 100 + 100 = 200 and uses one stop, city 1.
A direct flight 0 -> 2 does not exist, so this two-flight route is the cheapest.

Here is the flight graph. Each arrow is a one-way flight with its price.

🐢 Approach 1: Try Every Route (Brute Force)

The idea in one line: walk every possible path from the source and keep the cheapest one that lands on the destination.

The idea:

• Follow flights one by one from src.
• Carry the running cost and the flight count.
• Stop a path once it uses more than k + 1 flights.
• Keep the cheapest path that reaches dst.

Why it is weak:

• A busy network has a huge number of paths.
• The same city gets explored again through many different paths.
• Time grows exponentially. Too slow on a real graph.

Here is the DFS route search:

def find_cheapest_price(n, flights, src, dst, k):
    graph = [[] for _ in range(n)]
    for a, b, price in flights:
        graph[a].append((b, price))
    best = float("inf")
    def dfs(city, stops, cost):
        nonlocal best
        if city == dst:
            best = min(best, cost); return
        if stops > k or cost >= best:
            return
        for nxt, price in graph[city]:
            dfs(nxt, stops + 1, cost + price)
    dfs(src, -1, 0)
    return -1 if best == float("inf") else best

⚡ Approach 2: Bellman-Ford With a Stop Limit (Best)

The idea in one line: do exactly k + 1 relaxation passes, so each pass lets a path grow by one more flight.

The idea:

• Bellman-Ford finds shortest paths by relaxing every edge again and again.
• Relaxing an edge [u, v, w] means: if reaching u then paying w beats the current cost of v, update v.
• Each full pass over all edges lets paths grow by one more flight.

How it works:

• We allow k + 1 flights. So we do exactly k + 1 passes.
• After one pass: best cost using one flight.
• After two passes: best using up to two flights.
• After k + 1 passes: cheapest cost using at most k + 1 flights, which is k stops.
• In each pass, read costs from a copy of the previous pass.
• That copy stops one pass from chaining several flights and breaking the limit.

Why it is fast:

• Fixed k + 1 passes, each touching every flight once.
• Time is O(k × E). No path explosion.

Here is the stop-limited Bellman-Ford code:

def find_cheapest_price(n, flights, src, dst, k):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(k + 1):
        nxt = dist[:]
        for a, b, price in flights:
            if dist[a] + price < nxt[b]:
                nxt[b] = dist[a] + price
        dist = nxt
    return -1 if dist[dst] == float("inf") else dist[dst]

🧭 Approach 3: Dijkstra With a Stop Count (Alternative)

The idea in one line: run a cheapest-first search, but also carry how many stops each state used so you never exceed the limit.

The idea:

• Use a min-heap of states (cost, city, stops_used).
• Always pull the cheapest state next.
• Push a neighbor only if its stop count stays within k + 1 flights.

Why it works:

• The first time you pull dst off the heap, that cost is the answer.
• The stop count on each state blocks paths that use too many flights.

Why it is weak here:

• The stop limit can force you to keep a costlier path that uses fewer stops.
• So you may revisit the same city with different stop counts.
• The heap adds a log factor. Bellman-Ford is simpler when k is small.

Here are the two passes on the example. Each pass lets a route use one more flight.

Steps to Solve

1. Set the cost to every city as a large number, except the source which is zero.
2. Repeat the following k + 1 times, once per allowed flight.
3. Make a fresh copy of the current costs to read from.
4. For each flight [u, v, w], if the copy’s cost of u plus w is cheaper, update v in the working costs.
5. After all passes, look at the destination’s cost.
6. If it is still the large number, return -1. Otherwise return that cost.

#include <stdio.h>
#include <string.h>

#define INF 1000000000

int main(void) {
    int flights[][3] = {{0,1,100},{1,2,100},{2,3,100},{0,3,500}};
    int m = 4, n = 4, src = 0, dst = 2, k = 1;

    int cost[4];
    for (int i = 0; i < n; i++) cost[i] = INF;
    cost[src] = 0;

    for (int pass = 0; pass <= k; pass++) {  // k+1 passes
        int prev[4];
        memcpy(prev, cost, sizeof(cost));    // read from last pass
        for (int e = 0; e < m; e++) {
            int u = flights[e][0], v = flights[e][1], w = flights[e][2];
            if (prev[u] != INF && prev[u] + w < cost[v]) {
                cost[v] = prev[u] + w;       // cheaper way to reach v
            }
        }
    }

    printf("%d\n", cost[dst] == INF ? -1 : cost[dst]);
    return 0;
}

200

#include <iostream>
#include <vector>
using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights,
                      int src, int dst, int k) {
    const int INF = 1000000000;
    vector<int> cost(n, INF);
    cost[src] = 0;

    for (int pass = 0; pass <= k; pass++) {  // k+1 passes
        vector<int> prev = cost;             // read from last pass
        for (auto &f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (prev[u] != INF && prev[u] + w < cost[v]) {
                cost[v] = prev[u] + w;       // cheaper way to reach v
            }
        }
    }
    return cost[dst] == INF ? -1 : cost[dst];
}

int main() {
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{2,3,100},{0,3,500}};
    cout << findCheapestPrice(4, flights, 0, 2, 1) << endl;
    return 0;
}

200

import java.util.*;

public class Flights {
    public static int findCheapestPrice(int n, int[][] flights,
                                        int src, int dst, int k) {
        final int INF = 1000000000;
        int[] cost = new int[n];
        Arrays.fill(cost, INF);
        cost[src] = 0;

        for (int pass = 0; pass <= k; pass++) {   // k+1 passes
            int[] prev = cost.clone();            // read from last pass
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (prev[u] != INF && prev[u] + w < cost[v]) {
                    cost[v] = prev[u] + w;        // cheaper way to reach v
                }
            }
        }
        return cost[dst] == INF ? -1 : cost[dst];
    }

    public static void main(String[] args) {
        int[][] flights = {{0,1,100},{1,2,100},{2,3,100},{0,3,500}};
        System.out.println(findCheapestPrice(4, flights, 0, 2, 1));
    }
}

200

def find_cheapest_price(n, flights, src, dst, k):
    INF = float("inf")
    cost = [INF] * n
    cost[src] = 0                      # start city costs nothing

    for _ in range(k + 1):             # k stops means k+1 flights
        prev = cost[:]                 # snapshot of the last pass
        for u, v, w in flights:
            if prev[u] != INF and prev[u] + w < cost[v]:
                cost[v] = prev[u] + w  # cheaper way to reach v
    return -1 if cost[dst] == INF else cost[dst]


flights = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]]
print(find_cheapest_price(4, flights, 0, 2, 1))

200

function findCheapestPrice(n, flights, src, dst, k) {
  const INF = Infinity;
  let cost = new Array(n).fill(INF);
  cost[src] = 0; // start city costs nothing

  for (let pass = 0; pass <= k; pass++) {  // k+1 flights allowed
    const prev = cost.slice();             // snapshot of the last pass
    for (const [u, v, w] of flights) {
      if (prev[u] !== INF && prev[u] + w < cost[v]) {
        cost[v] = prev[u] + w;             // cheaper way to reach v
      }
    }
  }
  return cost[dst] === INF ? -1 : cost[dst];
}

const flights = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]];
console.log(findCheapestPrice(4, flights, 0, 2, 1));

200

Let us read the Python version line by line and see the reason for each part.

cost = [INF] * n
cost[src] = 0

cost[i] holds the cheapest price found so far to reach city i. Every city starts at infinity because we do not yet know any route. The source costs zero, since we begin there for free.

for _ in range(k + 1):

We run exactly k + 1 passes. Each pass lets a route use one more flight. With k stops we are allowed k + 1 flights. So k + 1 passes is the exact budget.

prev = cost[:]

This snapshot is the most important line. We copy the costs before the pass starts. Inside the pass we read prices from prev but write into cost. This stops a single pass from chaining several flights into one. Without the copy, an update could feed into another update in the same pass, and that would secretly use more flights than allowed.

for u, v, w in flights:
    if prev[u] != INF and prev[u] + w < cost[v]:
        cost[v] = prev[u] + w

We relax every flight. If city u was reachable in the previous pass, and flying u to v is cheaper than the current best for v, we update v. We check prev[u] != INF so we never build a price on top of an unreachable city.

return -1 if cost[dst] == INF else cost[dst]

After all passes, the destination’s cost is the cheapest price within the stop limit. If it is still infinity, no valid route exists, so we return -1.

Let us trace the example. We have k = 1, so two passes. Start with cost = [0, inf, inf, inf].

In pass one, prev = [0, inf, inf, inf]. Flight 0 -> 1 makes cost[1] = 100. Flight 0 -> 3 makes cost[3] = 500. The others read infinity, so they do nothing. Now cost = [0, 100, inf, 500].

In pass two, prev = [0, 100, inf, 500]. Flight 1 -> 2 makes cost[2] = 100 + 100 = 200. So cost[2] becomes 200. The answer for dst = 2 is 200.

⏱️ Time and Space Complexity

Let E be the number of flights. We do k + 1 passes, and each pass relaxes every flight once. So the time is O(k × E). The space holds the cost array and one copy per pass, which is O(n). This is a tidy fit because the stop limit k becomes the pass count.

🧩 Key Takeaways

• ✅ This is a shortest path problem with a limit on the number of flights.
• ✅ Bellman-Ford fits because each pass lets a route grow by exactly one flight.
• ✅ With k stops you run k plus one passes, since k stops means k plus one flights.
• ✅ Copy the costs each pass and relax from the copy, or flights chain and break the limit.
• ✅ It runs in O(k × E) time, where k is the stop limit and E is the number of flights.

🚀 What’s Next?

• Network Delay Time
• Min Cost to Connect All Points