Cheapest Flights Within K Stops Solution

Problem

Given a network of cities connected by one-way flights, find the cheapest way to travel from a source city to a destination city making at most k intermediate stops. If no valid route exists, return -1.

Input: n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1
Output: 700
Explanation: The path 0→1→3 costs 100+600=700 with 1 stop, which is within the limit. The cheaper path 0→1→2→3 costs only 400 but requires 2 stops, exceeding k=1.

Intuition

Think of this as a constrained shortest-path problem: we want the minimum-cost route, but we're only allowed to hop through at most k intermediate cities. The key insight is that after exactly t flights, we know the cheapest way to reach every city using at most t flights — and we can compute the t+1 solution from the t solution by trying every available flight. Since k stops means k+1 flights, we only need to run this process k+1 times.

Approach 1 — Bellman-Ford (Limited Relaxations)

Run exactly k+1 rounds of Bellman-Ford edge relaxation. Each round represents taking one more flight. The snapshot of prices from the previous round prevents "chaining" multiple relaxations within the same round, which would violate the stop limit.

Initialize a cheapest_to array with infinity for all cities; set cheapest_to[src] = 0.
Repeat k+1 times (once per allowed flight): a. Snapshot the current cheapest_to array as prev_cheapest. b. For every flight (from, to, price), if prev_cheapest[from] is reachable, update cheapest_to[to] = min(cheapest_to[to], prev_cheapest[from] + price).
Return cheapest_to[dst], or -1 if it's still infinity.

1def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
2    INF = float('inf')
3    cheapest_to = [INF] * n
4    cheapest_to[src] = 0
5
6    for _ in range(k + 1):  # k stops = k+1 flights
7        # Snapshot prevents same-round updates from chaining together (would exceed k stops)
8        prev_cheapest = cheapest_to.copy()
9        for from_city, to_city, price in flights:
10            if prev_cheapest[from_city] < INF:
11                cheapest_to[to_city] = min(cheapest_to[to_city], prev_cheapest[from_city] + price)
12
13    return cheapest_to[dst] if cheapest_to[dst] < INF else -1

Time: O(k × |flights|) — we process every edge once per round, for k+1 rounds.

Space: O(n) — two arrays of size n (current and previous).

Approach 2 — Dijkstra with State Tracking

Model the search state as (city, flights_taken) and use a min-heap to always expand the cheapest known state first. Once we reach the destination, that first arrival is guaranteed to be the cheapest (by Dijkstra's property).

Build an adjacency list from the flights.
Push (cost=0, city=src, flights_taken=0) onto a min-heap.
Track seen[city][flights_taken] to avoid reprocessing the same state.
Each time we pop a state: if it's the destination, return the cost; if we've taken fewer than k+1 flights, push all neighbors with flights_taken + 1.
Return -1 if the heap empties without reaching the destination.

1import heapq
2from collections import defaultdict
3
4def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
5    graph = defaultdict(list)
6    for from_city, to_city, price in flights:
7        graph[from_city].append((to_city, price))
8
9    heap = [(0, src, 0)]  # (total_cost, city, flights_taken)
10    seen = {}  # (city, flights_taken) -> ensures we don't reprocess cheaper-cost duplicates
11
12    while heap:
13        cost, city, flights_taken = heapq.heappop(heap)
14
15        if city == dst:
16            return cost
17
18        if (city, flights_taken) in seen:
19            continue
20        seen[(city, flights_taken)] = cost
21
22        if flights_taken <= k:  # still allowed to board one more flight
23            for neighbor, price in graph[city]:
24                if (neighbor, flights_taken + 1) not in seen:
25                    heapq.heappush(heap, (cost + price, neighbor, flights_taken + 1))
26
27    return -1

Time: O(k × E × log(k × n)) — each (city, flights_taken) state is pushed at most once, and heap operations cost log of the heap size.

Space: O(k × n) — the seen table and heap can hold up to k+1 entries per city.

Complexity Summary

Approach	Time	Space	When to use
Bellman-Ford	O(k × \|flights\|)	O(n)	Simpler to implement; preferred when code clarity matters more than early exit
Dijkstra	O(k × E × log(k × n))	O(k × n)	Better in practice when the destination is found early, avoiding many relaxations

Common Mistakes

Not copying the previous round's prices — updating cheapest_to in-place while reading from it means a city relaxed earlier in the same round can cascade to relax others within the same iteration, effectively using fewer rounds than intended and producing wrong answers for paths that require exactly k+1 flights.
Off-by-one on the round count — k stops means k+1 flights, so the loop must run k+1 times. Running it k times gives the answer for k-1 stops, not k.
Integer overflow when using MAX_VALUE as infinity — in C++ and Java, adding a flight price to INT_MAX wraps around to a negative number, corrupting comparisons. Use INT_MAX / 2 as the sentinel or check for infinity before adding.
Forgetting the flight limit in Dijkstra — without the flightsTaken <= k guard, the algorithm can find paths through more than k stops and return a cheaper-but-invalid answer.
Treating k=0 as "no route possible" — k=0 means only direct flights are allowed (zero intermediate stops). The algorithm handles this correctly: with a single round of relaxation, only direct edges from src are processed.

Cheapest Flights Within K Stops — Solution