Cheapest Flights Within K Stops

public class Solution {
    public Integer findCheapestPrice(Integer n, int[][] flights, Integer src, Integer dst, Integer k) {
        // Your code goes here
    }
}

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:

1. Start from the source with distance 0
2. Always pick the cheapest unvisited node
3. Update distances to its neighbors
4. 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:

1. Start at city 0 with cost $0
2. Process city 1 (cost $10), then city 2 (cost $20 via 0→1→2)
3. Mark city 2 as "visited" with cost $20
4. 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:

1. Initialize: Add (0, src, 0) to a min-heap (zero cost at source, zero stops used)
2. Process states: Pop the cheapest state (cost, city, stops) from the heap
3. Check destination: If city == dst, it means we found the cheapest valid route so return cost
4. Check constraint: If stops > k, this path exceeds the limit so skip it
5. Explore neighbors: For each neighbor, add (cost + price, neighbor, stops + 1) to the heap
6. 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.

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.

Solution

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;
}

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: