Cheapest Flights Within K Stops

There are n airports numbered 0 to n - 1. Each entry flights[i] = [from, to, price] is a one-way flight from airport from to airport to that costs price.

Find the lowest total price of a trip from src to dst that makes at most k stops. A stop is an intermediate airport where you change planes, so a trip with k stops uses at most k + 1 flights. If no such trip exists, return -1.

Example 1

Example 2

Example 3

Constraints

• 2 <= n <= 100
• 0 <= flights.length <= n * (n - 1) / 2
• flights[i].length == 3
• 0 <= from, to < n, from != to
• 1 <= price <= 104
• There is at most one flight between any ordered pair of airports.
• 0 <= src, dst, k < n, src != dst

Pattern Path · Graphs: Traversal · problem 136 of 169

Start simple

Enumerate every route of up to k + 1 flights with DFS and keep the cheapest: exponential, roughly O(n^(k+1)) in the worst case.

The key idea

The stop limit is really a limit on the number of flights: at most k + 1. That suggests building answers by flight count. Let cost[v] be the cheapest price to reach v using at most r flights. Initially (r = 0) only src is reachable, at price 0.

To go from r to r + 1 flights, try extending every known route by one flight: for each [u, v, p], the price cost[u] + p is a candidate for v. This is one round of the Bellman-Ford algorithm, capped at k + 1 rounds.

The key detail is to read from the previous round and write into a copy. If you update in place, a price you just lowered this round can be extended again in the same round, so one round might secretly use two or three flights and break the stop limit. With the copy, round r reflects exactly "at most r flights".

After k + 1 rounds, cost[dst] is the answer, or -1 if it is still infinite. Each round scans all E flights, so the total is O(k · E).

Complexity

• Time: O(k · E)
• Space: O(n)

Python

from math import inf


class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        # cost[v] = cheapest price to reach v using at most r flights (r = rounds so far).
        cost = [inf] * n
        cost[src] = 0

        for _ in range(k + 1):              # k stops means at most k + 1 flights
            next_cost = cost[:]             # read from the old round, write into a copy
            for u, v, price in flights:
                if cost[u] + price < next_cost[v]:
                    next_cost[v] = cost[u] + price
            cost = next_cost

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

JavaScript

var findCheapestPrice = function(n, flights, src, dst, k) {
  // cost[v] = cheapest price to reach v using at most r flights (r = rounds so far).
  let cost = new Array(n).fill(Infinity);
  cost[src] = 0;

  for (let round = 0; round <= k; round++) {   // k stops means at most k + 1 flights
    const nextCost = cost.slice();             // read from the old round, write into a copy
    for (const [u, v, price] of flights) {
      if (cost[u] + price < nextCost[v]) nextCost[v] = cost[u] + price;
    }
    cost = nextCost;
  }

  return cost[dst] === Infinity ? -1 : cost[dst];
};

What the interviewer is checking

It tests whether you see why ordinary Dijkstra breaks under an extra constraint, and whether you can adapt a shortest-path algorithm by adding a dimension (here, flights used) to the state.

Mistakes to avoid

• Running standard Dijkstra with a visited set: the cheapest way into an airport may use too many stops, and the slightly pricier way with fewer stops is then never explored.
• Updating prices in place during a Bellman-Ford round, which lets one round use several flights.
• Confusing stops with flights: k stops allows k + 1 flights.
• Returning infinity instead of -1 when dst is unreachable.

Follow-ups to expect

• Can you use a heap? (Dijkstra on (airport, stops) states.)
• What if you also need the route itself? (Store a predecessor per round.)
• What if prices could be negative? (Bellman-Ford rounds still work.)

In real software

Travel search engines and network routing protocols such as RIP compute cheapest paths under a hop limit; RIP literally runs distance-vector rounds and treats more than 15 hops as unreachable.

Practice next