loading

Cheapest Flights Within K Stops — Step-by-Step Visualization

mediumLeetCode #787GraphBreadth-First SearchShortest PathHeap (Priority Queue)Dynamic Programming

There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [from_i, to_i, price_i]` indicates that there is 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`.

Algorithm Pattern

Modified Bellman-Ford or BFS

Key Idea

Since we have a constraint on the number of stops (`k`), we can use the Bellman-Ford algorithm and run it for exactly `k + 1` iterations. Alternatively, a BFS approach where we process the graph level by level (where each level corresponds to an additional stop) also works. Dijkstra can be tricky because a more expensive path with fewer stops might eventually be better after more processing.

Step-by-Step Approach

  1. Initialize `prices = [infinity] * n`, `prices[src] = 0`.
  2. Iterate `k + 1` times:
  3. Create a copy of the current prices `tmpPrices`.
  4. For each flight `(u, v, w)`:
  5. If `prices[u] == infinity`, continue.
  6. If `prices[u] + w < tmpPrices[v]`:
  7. `tmpPrices[v] = prices[u] + w`.
  8. Update `prices = tmpPrices`.
  9. Return `prices[dst]` if it is not infinity, else `-1`.

Common Gotchas

  • Wait until a complete iteration is done before updating `prices` with `tmpPrices` to ensure you don't take more than one flight in a single 'stop' iteration.
  • k stops means at most k + 1 edges.

Related Problems

← All problems