LeetCode 787 · Medium · Advanced Graphs

Cheapest Flights Within K Stops

Cities 0..n−1 are joined by one-way flights (from, to, price). Return the cheapest price from src to dst using at most k stops in between, or -1 if no such route exists.

O(k · E)time
O(n)space
Bellman-Fordk + 1 rounds

flights separated by ";" · up to 10 · cities 0..n−1 · n: 1–6 · price 1 to 999 · k: 0 to 3 · src ≠ dst

prices · frozen for this round (read)

tmpPrices · this round's results (written)

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { int inf = Integer.MAX_VALUE; int[] prices = new int[n]; Arrays.fill(prices, inf); prices[src] = 0; for (int i = 0; i <= k; i++) { // round i: <= i+1 flights int[] tmpPrices = prices.clone(); for (int[] f : flights) { int s = f[0]; int d = f[1]; int p = f[2]; if (prices[s] == inf) { continue; } if (prices[s] + p < tmpPrices[d]) { tmpPrices[d] = prices[s] + p; } } prices = tmpPrices; } return prices[dst] == inf ? -1 : prices[dst];}
i
—
(s, d, p)
—
prices[s] + p
—
tmpPrices[d]
—

Why it works

  1. Brute force enumerates every route of at most k + 1 flights by DFS: up to O(dᵏ⁺¹) for out-degree d.
  2. Round i finds the cheapest routes of at most i + 1 flights. Each round extends every known route by exactly one flight. After k + 1 rounds, prices[dst] is the cheapest route with at most k stops.
  3. Why the copy: every relaxation reads the frozen prices and writes tmpPrices. Writing straight into prices would let one round chain several flights, quietly breaking the stop limit. The continue on an unreachable city also protects the sum: Integer.MAX_VALUE + p would overflow to a negative number. In the "why the copy" preset, the route 0→3→1→4→2 costs 6 but needs 4 flights; with k = 2 the answer must be 7.
  4. Cost: k + 1 rounds over all E flights: O(k · E) time, two arrays of n prices: O(n) space.
  5. Pitfall: plain Dijkstra ignores the stop count: it settles a city by its cheapest price even if that route used too many stops. Related: Network Delay Time (743) is the unconstrained Dijkstra version.