Cheapest Flight within k Stops

Problem Statement

You are given:

n cities numbered from 0 to n - 1
A list of flights where flights[i] = [fromi, toi, pricei]
Two integers: src and dst (source and destination)
An integer k, the maximum number of stops allowed (i.e., you can take at most k + 1 flights)

Goal

Return the cheapest price from src to dst with at most k stops.
If no such route exists, return -1.

Examples

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:
- You can go directly from 0 to 3 with cost 500 (0 stops)
- Or 0 → 1 → 2 → 3 with cost 300 (2 stops), which is invalid since it exceeds k=1

Example 2

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

Output:
200

Explanation:
- 0 → 1 → 2 (1 stop) with total cost = 200

Why Not Use Dijkstra?

In Dijkstra's algorithm, once we visit a node, we typically don't revisit it.
But in this problem, a cheaper route to a node might be found through another path that uses fewer or more stops.

Therefore, we use a variation of BFS known as Dijkstra with constraints or Bellman-Ford-like BFS.

Approach: Modified BFS (Dijkstra-like with Queue)

We use a priority queue (or normal queue) and track:

Current node
Cost so far
Stops so far

We prune paths if:

The number of stops exceeds k
The cost is more than the current best for that node with the same or fewer stops

Java Code (Using PriorityQueue)

class Solution {
    class Pair {
        int node, cost, stops;
        Pair(int node, int cost, int stops) {
            this.node = node;
            this.cost = cost;
            this.stops = stops;
        }
    }

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Build adjacency list
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] flight : flights) {
            adj.computeIfAbsent(flight[0], x -> new ArrayList<>()).add(new int[]{flight[1], flight[2]});
        }

        // Min-heap: compare based on cost
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        pq.add(new Pair(src, 0, 0));

        int[] minStops = new int[n];
        Arrays.fill(minStops, Integer.MAX_VALUE);
        minStops[src] = 0;

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            int node = cur.node;
            int cost = cur.cost;
            int stops = cur.stops;

            if (node == dst) return cost;

            if (stops > k || stops > minStops[node]) continue;
            minStops[node] = stops;

            if (!adj.containsKey(node)) continue;

            for (int[] neighbor : adj.get(node)) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];
                pq.add(new Pair(nextNode, cost + weight, stops + 1));
            }
        }

        return -1;
    }
}

Dry Run

Input

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

Step-by-Step Execution

Start at node 0 with cost 0, stops 0
From 0 → 1 with cost 100, stops = 1
From 0 → 2 with cost 500, stops = 1
From 1 → 2 with cost = 100 + 100 = 200, stops = 2 → valid since stops ≤ k

Final answer: 200

Time and Space Complexity

Time Complexity

Each node can be processed multiple times with different stop counts
Each edge may be traversed for each level of stops
PriorityQueue operations are log(V), so the time complexity is:

O(E * log V)

Space Complexity

O(V + E) for adjacency list
O(V) for tracking minimum stops
O(V) for queue size

Alternative: Bellman-Ford (K Iterations)

Use dynamic programming or Bellman-Ford idea to relax edges k + 1 times.

Pros

Simpler to code
Time complexity: O(K * E)

Why PriorityQueue Over Queue?

Regular BFS with queue explores level by level but not by cost
PriorityQueue ensures lower-cost paths are explored first, helping with early pruning

Why Not TreeSet?

TreeSet does not allow duplicate entries, which is problematic in this problem
Also requires custom comparator, equals, and hashCode
PriorityQueue is more appropriate and easier to work with in this scenario

Conclusion

Use a priority queue with (node, cost, stops) for better pruning
A Bellman-Ford-like approach also works and can be more efficient for small k
Always track stops separately from cost because lower cost might come from a longer path