Graph DSA: Cheapest Flights Within $K$ Stops

1. Problem Statement & Overview

The Cheapest Flights Within $K$ Stops problem is a classic graph traversal challenge frequently applied in real-world routing engines, flight aggregators, and navigation systems. Given $n$ cities (nodes) and a collection of directed flights where each flight connects a source to a destination with a specific monetary price, our objective is to find the cheapest price to travel from a designated Source to a designated Destination with at most $K$ stops.

If no such route exists within the specified stop constraint, the algorithm must return -1.

Formal Input Parameters

• $n$: Total number of cities/nodes.
• flights: An array of directed edges where flights[i] = [from, to, price].
• src: Starting city.
• dst: Target destination city.
• K: Maximum number of intermediate stops allowed.

2. Why Standard Dijkstra's Algorithm Fails Here

At first glance, finding the shortest (cheapest) path in a weighted graph immediately points toward Dijkstra's Algorithm using a Min-Priority Queue. However, applying standard Dijkstra directly to this problem leads to incorrect results due to the stop constraint ($K$).

The Flaw of Greedy Cost Minimization

Dijkstra's algorithm greedily extracts the node with the minimum accumulated cost from the priority queue.

• Suppose Path A reaches an intermediate node with a very low cost but has already consumed all $K$ stops. Because its stops are maxed out, it cannot make any further transitions to reach the final destination.
• Simultaneously, suppose Path B reaches the same intermediate node with a higher cost, but it has consumed fewer stops (e.g., only 1 stop out of $K=2$). Path B has the flexibility to make another hop to reach the destination.

Standard Dijkstra will prune or ignore Path B because its cost is higher than Path A at that intermediate node. Consequently, the algorithm misses the valid path and returns an incorrect answer or -1.

Note: In Dijkstra's algorithm, we prioritize nodes by distance/cost. For this problem, because the number of allowable transitions is strictly bounded by $K$, our primary ordering metric must shift from accumulated cost to number of stops taken.

3. Core Mental Model: BFS with Level-Order Transition

Since every flight edge transition increments our stop counter by exactly +1, the increase in stops is constant and uniform. This structural property mirrors a Breadth-First Search (BFS) level-order traversal, eliminating the need for a costly Min-Priority Queue.

Real-Life Analogy: The Multi-Leg Flight Booking

Imagine booking a multi-leg journey where airlines charge different ticket prices.

• You want the cheapest ticket, but your employer imposes a strict travel policy: "You can change planes at most $K$ times."
• If you find a cheap ticket that forces you to change planes 4 times when $K=2$, that ticket is useless.
• Conversely, a slightly more expensive ticket that only requires 1 plane change is fully compliant and gets you to your destination.
• We must track paths by how many connections (stops) they make rather than blindly picking the cheapest intermediate sub-route.

4. Why a Standard Queue Beats a Priority Queue

Because the number of stops increases by a constant increment (+1 at each step), a standard FIFO Queue naturally processes paths in increasing order of stops:

1. All paths with 0 stops are processed first.
2. Followed by all paths with 1 stop.
3. Followed by all paths with 2 stops, up to $K$.

By switching from a Priority Queue ($\mathcal{O}(E \log V)$) to a standard Queue ($\mathcal{O}(V + E)$), we eliminate the logarithmic sorting overhead while guaranteeing that we evaluate paths ordered by their depth (stops).

5. Step-by-Step Algorithm Evolution

1. Graph Construction: Build an adjacency list from the flights array. Each entry stores connected neighbor nodes along with their flight prices (edge weights).
2. Distance / Cost Tracking Array: Maintain a distance array (dist) initialized to infinity (1E9) to record the minimum cost found so far to reach each node.
3. Queue Initialization: Push a state tuple into the Queue: (stops_taken, current_node, current_cost).
   • Initial state: (0, src, 0) (0 stops, starting at source, with 0 accumulated cost).
4. Queue Processing Loop: While the queue is not empty:
   • Pop the front element representing (stops, node, cost).
   • Stop Constraint Check: If stops > K, continue (do not explore neighbors further, as we have exceeded the maximum allowed stops).
   • Iterate over all adjacent neighbors of the current node.
   • For each neighbor, calculate new_cost = cost + edge_weight.
   • Relaxation Condition: If new_cost < dist[neighbor], update dist[neighbor] = new_cost and push the new state (stops + 1, neighbor, new_cost) into the queue.
5. Destination Evaluation: Do not terminate immediately upon reaching the destination for the first time. Continue processing the queue because a later path with fewer stops or a better overall cost configuration might update the destination price.
6. Final Result: After the queue is exhausted, check dist[dst]. If it remains 1E9, return -1; otherwise, return dist[dst].

6. Implementation (C++ and Java)

Below are the complete, production-grade implementations in C++ and Java matching the optimized BFS queue approach.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // Step 1: Create adjacency list graph (node -> list of {neighbor, price})
        vector<vector<pair<int, int>>> adj(n);
        for (auto& flight : flights) {
            adj[flight[0]].push_back({flight[1], flight[2]});
        }
        
        // Queue stores: {stops, {node, cost}}
        queue<pair<int, pair<int, int>>> q;
        q.push({0, {src, 0}});
        
        // Distance array to store minimum cost to reach each node
        vector<int> dist(n, 1e9);
        dist[src] = 0;
        
        while (!q.empty()) {
            auto it = q.front();
            q.pop();
            
            int stops = it.first;
            int node = it.second.first;
            int cost = it.second.second;
            
            // If stops exceed k, we cannot take further flights from this node
            if (stops > k) continue;
            
            for (auto& neighborPair : adj[node]) {
                int adjNode = neighborPair.first;
                int edgeWeight = neighborPair.second;
                
                // If we found a cheaper path to adjNode, update and push to queue
                if (cost + edgeWeight < dist[adjNode] && stops <= k) {
                    dist[adjNode] = cost + edgeWeight;
                    q.push({stops + 1, {adjNode, dist[adjNode]}});
                }
            }
        }
        
        // If destination was never reached, return -1
        if (dist[dst] == 1e9) return -1;
        return dist[dst];
    }
};

Java Implementation

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Step 1: Create adjacency list graph
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] flight : flights) {
            adj.get(flight[0]).add(new int[] { flight[1], flight[2] });
        }
        
        // Queue stores state: [stops, node, cost]
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { 0, src, 0 });
        
        // Distance array initialized to infinity
        int[] dist = new int[n];
        Arrays.fill(dist, 1000000000);
        dist[src] = 0;
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int stops = curr[0];
            int node = curr[1];
            int cost = curr[2];
            
            if (stops > k) continue;
            
            for (int[] neighbor : adj.get(node)) {
                int adjNode = neighbor[0];
                int edgeWeight = neighbor[1];
                
                if (cost + edgeWeight < dist[adjNode] && stops <= k) {
                    dist[adjNode] = cost + edgeWeight;
                    q.offer(new int[] { stops + 1, adjNode, dist[adjNode] });
                }
            }
        }
        
        return dist[dst] == 1000000000 ? -1 : dist[dst];
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Problem Core: Finding the cheapest path under a strict upper bound of intermediate stops ($K$) requires careful state management beyond standard shortest-path algorithms.
• Why Dijkstra Fails Here: Dijkstra prioritizes accumulated cost greedily. A path with a low cost might consume all $K$ stops prematurely, blocking further travel, while a slightly costlier path with fewer stops could lead to a cheaper overall valid route.
• Uniform Increment Property: Because every flight step increases the stop count by exactly +1, a standard FIFO Queue operates as a natural level-order traversal.
• Eliminating Priority Queues: Replacing a Min-Priority Queue with a standard Queue removes unnecessary logarithmic overhead ($\log V$), resulting in faster execution.
• Destination Handling: Never terminate search early upon first reaching the destination node; alternative paths explored later in the queue may yield a cheaper valid cost within the $K$ stop limit.
• Distance Array Initialization: Always initialize distance lookup tables with a sufficiently large sentinel value (1E9) to accurately detect unreachable destination nodes (-1).