Cheapest Flights K Stops

Problem

A travel booking system needs to find the lowest-cost route between airports. You’re given n cities connected by flights, where each flight [from, to, price] represents a direct route with its cost.

Find the cheapest route from src to dst that uses at most k layovers (intermediate cities). If no such route exists, return -1.

Note: A route with k layovers means visiting k intermediate cities, or equivalently, taking k+1 flights.

Example 1

Input:

n = 4
flights = [[0,1,100], [1,2,100], [2,3,100], [0,3,500]]
src = 0
dst = 3
k = 1

Output:

500

Explanation: The route 0→1→2→3 costs $300 with 2 layovers (cities 1 and 2), which exceeds k=1. The direct flight 0→3 costs $500 with 0 layovers. Even though it’s more expensive, it’s the only valid route.

Example 2

Input:

n = 4
flights = [[0,1,100], [1,2,100], [2,3,100]]
src = 0
dst = 3
k = 1

Output:

-1

Explanation: The only path 0→1→2→3 requires 2 layovers (cities 1 and 2), but we’re limited to k=1. No valid route exists.

Explanation

Understanding the Problem

A flight booking system needs to find the cheapest route between cities, but travelers have a constraint: they don’t want too many layovers. Given a network of flights with prices and a maximum number of stops allowed, find the minimum cost to reach the destination.

The key constraint is the stop limit. A “stop” is an intermediate city, so flying A→B→D has 1 stop (city B). If k=1, both routes above are valid. If k=0, only direct flights work.

First Intuition: Can We Use Dijkstra?

This is a shortest path problem. We need to find the cheapest route from source to destination. In Network Delay Time, we used Dijkstra’s algorithm to find shortest paths. The algorithm worked beautifully:

• Start from the source with distance 0
• Always pick the cheapest unvisited node
• Update distances to its neighbors
• Once a node is processed, we have its optimal distance

Let’s try applying the same approach here. We’ll track the minimum cost to reach each city and greedily process the cheapest path first.

Testing Standard Dijkstra

Consider this example: Find the cheapest route from city 0 to city 3 with at most k=1 stops.

Why Standard Dijkstra Fails

The issue: Standard Dijkstra only tracks one value per city, i.e. the minimum cost to reach it. Once we mark a city as “visited” with its cheapest cost, we never reconsider it.

In the example above, standard Dijkstra would process cities in order of increasing cost:

• Start at city 0 with cost $0
• Process city 1 (cost $10), then city 2 (cost $20 via 0→1→2)
• Mark city 2 as “visited” with cost $20
• Reach city 3 with cost $30 via the 0→1→2→3 path

But there’s also a more expensive way to reach city 2 which is directly from city 0 for $50. Standard Dijkstra would ignore this path because city 2 is already visited with a cheaper cost of $20.

But, the $50 path to city 2 only uses 1 stop, making the route 0→2→3 valid for k=1 (total cost $60). The cheaper $20 path uses 2 stops, making 0→1→2→3 invalid for k=1.

Standard Dijkstra greedily picks the cheapest path and misses the valid but more expensive alternative.

The Solution: Track Both City and Stops

We need to track not just “minimum cost to city X” but “minimum cost to city X using exactly S stops”. This means our state must include both:

• State: (cost, city, stops_used)
• Heap: min-heap ordered by cost (same as Dijkstra)
• Visited tracking: best[(city, stops)] = minimum cost to reach city having used exactly stops flights

This creates a state space where the same city can be visited multiple times with different stop counts. Each (city, stops) pair is treated as a distinct state.

How the Algorithm Works

With this modified state, the algorithm becomes:

• Initialize: Add (0, src, 0) to a min-heap (zero cost at source, zero stops used)
• Process states: Pop the cheapest state (cost, city, stops) from the heap
• Check destination: If city == dst, it means we found the cheapest valid route so return cost
• Check constraint: If stops > k, this path exceeds the limit so skip it
• Explore neighbors: For each neighbor, add (cost + price, neighbor, stops + 1) to the heap
• Avoid redundancy: Track best[(city, stops)] to skip states we’ve seen with lower cost

Because the heap is ordered by cost, the first time we pop the destination city, we’re guaranteed it’s the cheapest path that satisfies the stop constraint.

This pattern of extending Dijkstra’s state with additional constraints appears in many problems: shortest path with fuel limits, paths that must visit certain checkpoints, or paths with time windows. The key is identifying which extra dimension needs tracking.

Walkthrough

Let’s trace through flights = [[0,1,100], [1,2,100], [2,3,100], [0,3,500]] with src=0, dst=3, k=1:

Step 1: Initialize

We start at city 0 with no cost and no stops used yet. Our min-heap contains just one state: (0, city=0, stops=0).

Step 2: Process city 0

We pop (0, 0, 0) from the heap. City 0 isn’t the destination, so we explore its outgoing flights:

• Flight to city 1 costs $100: add (100, 1, 1) to heap
• Flight to city 3 costs $500: add (500, 3, 1) to heap

Step 3: Process city 1

The min-heap pops (100, 1, 1) since it has the lowest cost. From city 1, we can fly to city 2 for $100, giving total cost $200. We add (200, 2, 2) to the heap.

Now the heap contains (200, 2, 2) and (500, 3, 1). Notice that the state (200, 2, 2) has lower cost but uses 2 flights (stops=2).

Step 4: Skip city 2 (exceeds stop limit)

The heap pops (200, 2, 2). City 2 isn’t the destination, so we check the stop constraint: stops=2 > k=1. We’ve already used 2 flights to get here (0→1→2), which means going any further would exceed our budget of 1 intermediate stop. Skip this state entirely, we don’t even look at city 2’s neighbors.

Step 5: Found valid path

The heap pops (500, 3, 1). City 3 is the destination, so we immediately return cost=500. This is the direct flight 0→3, which uses just 1 flight and 0 intermediate stops, well within our k=1 limit.

Stop counting can be confusing! In this problem, k represents the maximum number of intermediate cities (layovers), not the number of flights. A path with k stops traverses k+1 edges. Our algorithm tracks stops_used which increments with each flight taken. The destination check (city == dst) comes before the stop limit check (stops > k). This ordering matters: a valid path to the destination can have up to k+1 flights (k intermediate stops), and the stop limit check only gates whether we explore further from non-destination cities.

Solution

def find_cheapest_flight(flights, n, src, dst, max_stops):
    graph = defaultdict(list)
    for u, v, cost in flights:
        graph[u].append((v, cost))
    
    # (cost, city, stops_used)
    heap = [(0, src, 0)]
    # best[city][stops] = min cost to reach city with exactly stops
    best = {}
    
    while heap:
        cost, city, stops = heappop(heap)
        
        if city == dst:
            return cost
        
        if stops > max_stops:
            continue
        
        if (city, stops) in best and best[(city, stops)] <= cost:
            continue
        best[(city, stops)] = cost
        
        for neighbor, price in graph[city]:
            new_cost = cost + price
            heappush(heap, (new_cost, neighbor, stops + 1))
    
    return -1

public int findCheapestFlight(int[][] flights, int n, int src, int dst, int maxStops) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] f : flights) {
        graph.computeIfAbsent(f[0], k -> new ArrayList<>()).add(new int[]{f[1], f[2]});
    }
    
    // {cost, city, stopsUsed}
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    heap.offer(new int[]{0, src, 0});
    Map<String, Integer> best = new HashMap<>();
    
    while (!heap.isEmpty()) {
        int[] curr = heap.poll();
        int cost = curr[0], city = curr[1], stops = curr[2];
        
        if (city == dst) return cost;
        
        if (stops > maxStops) continue;
        
        String key = city + "," + stops;
        if (best.containsKey(key) && best.get(key) <= cost) continue;
        best.put(key, cost);
        
        for (int[] next : graph.getOrDefault(city, new ArrayList<>())) {
            int newCost = cost + next[1];
            heap.offer(new int[]{newCost, next[0], stops + 1});
        }
    }
    
    return -1;
}

func findCheapestFlight(flights [][]int, n, src, dst, maxStops int) int {
    graph := make(map[int][][2]int)
    for _, f := range flights {
        graph[f[0]] = append(graph[f[0]], [2]int{f[1], f[2]})
    }
    
    // MinHeap: (cost, city, stops)
    h := &FlightHeap{{0, src, 0}}
    heap.Init(h)
    best := make(map[[2]int]int)
    
    for h.Len() > 0 {
        curr := heap.Pop(h).([3]int)
        cost, city, stops := curr[0], curr[1], curr[2]
        
        if city == dst {
            return cost
        }
        
        if stops > maxStops {
            continue
        }
        
        key := [2]int{city, stops}
        if v, ok := best[key]; ok && v <= cost {
            continue
        }
        best[key] = cost
        
        for _, next := range graph[city] {
            newCost := cost + next[1]
            heap.Push(h, [3]int{newCost, next[0], stops + 1})
        }
    }
    
    return -1
}

function findCheapestFlight(
    flights: number[][], n: number, src: number, dst: number, maxStops: number
): number {
    const graph = new Map<number, [number, number][]>();
    for (const [u, v, cost] of flights) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push([v, cost]);
    }
    
    const heap: [number, number, number][] = [[0, src, 0]];
    const best = new Map<string, number>();
    
    while (heap.length > 0) {
        heap.sort((a, b) => a[0] - b[0]);
        const [cost, city, stops] = heap.shift()!;
        
        if (city === dst) return cost;
        
        if (stops > maxStops) continue;
        
        const key = `${city},${stops}`;
        if (best.has(key) && best.get(key)! <= cost) continue;
        best.set(key, cost);
        
        for (const [neighbor, price] of graph.get(city) ?? []) {
            const newCost = cost + price;
            heap.push([newCost, neighbor, stops + 1]);
        }
    }
    
    return -1;
}

When to Use This Pattern

This modified Dijkstra with state extension is useful in these scenarios:

Alternative: Bellman-Ford Approach

An alternative is to use a Bellman-Ford variant: run k+1 iterations, where each iteration relaxes all edges. This gives O(k · E) time complexity. For small k with many edges, this can be more efficient. However, the Dijkstra approach is more intuitive and generalizes better to other constraint types.

Connection to Network Delay Time

Both problems use shortest path algorithms, but: