Cheapest Flights Within K Stops
Given n cities, directed flights with prices, a source, a destination and an integer k, return the cheapest price from source to destination using at most k intermediate stops. Return -1 if no such route exists.
- 1 ≤ n ≤ 100
- 0 ≤ flights.length ≤ (n · (n - 1) / 2)
- 1 ≤ price ≤ 10^4
- 0 ≤ k < n
- Weighted shortest path with a hop limit
- Plain Dijkstra fails: the cheapest path to a city may use too many stops
- Relax edges in rounds, at most k+1 rounds
Once edges have different costs, BFS order is wrong and you need to expand nodes by accumulated distance: Dijkstra with a min-heap for non-negative weights. Negative weights or a "at most k edges" bound push you to Bellman-Ford (k rounds of relaxation); "every pair" on a small dense graph is Floyd-Warshall.
Run k + 1 rounds of Bellman-Ford style relaxation. In each round, work from a copy of the previous distances so that a round extends every path by exactly one edge; relax all flights against that snapshot. After k + 1 rounds the destination's distance is the cheapest price using at most k + 1 flights, or -1 if still infinite. The snapshot is what prevents chaining several edges in a single round.
- Dijkstra on the state
(city, stops used)is correct and often faster, since it explores O(n · k) states. BFS layer by layer with pruning also works given unit hop counts.