Cheapest Flights Within K Stops

LeetCode 787: Cheapest Flights Within K Stops Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a modified Bellman-Ford algorithm (or BFS with layer tracking) to iteratively relax edge weights exactly k + 1 times, ensuring we find the minimum cost without exceeding the stop limit.

The problem asks us to find the cheapest path between a source city (src) and a destination city (dst) in a weighted directed graph. The critical constraint is that the path cannot include more than k stops. This means the path can consist of at most k + 1 flights (edges). If no such path exists, we must return -1.

This is a classic variation of the shortest path problem found in LeetCode 787: Cheapest Flights Within K Stops, often used in technical interviews to test understanding of graph algorithms beyond standard Dijkstra implementations.

Brute Force Approach for Cheapest Flights Within K Stops

The brute force method involves exploring every possible path from the source to the destination using Depth-First Search (DFS). We traverse the graph recursively, accumulating the total cost. If the number of stops exceeds k, we backtrack. Among all valid paths found, we track the minimum cost.

Naive DFS Pseudo-code:

function dfs(current_city, current_cost, stops_remaining):
    if current_city == dst:
        return current_cost
    if stops_remaining < 0:
        return infinity
    
    min_cost = infinity
    for neighbor, price in flights[current_city]:
        cost = dfs(neighbor, current_cost + price, stops_remaining - 1)
        min_cost = min(min_cost, cost)
    
    return min_cost

Complexity Analysis: The time complexity is roughly $O(N^{K+1})$ in the worst case (where $N$ is the number of cities), as the branching factor can be up to $N$.

Why it fails: This approach fails due to Time Limit Exceeded (TLE) errors on larger inputs. The recursion explores many overlapping subproblems and redundant paths. Standard DFS does not inherently prioritize cheaper paths or prune expensive paths efficiently enough without memoization, and even with memoization, the state space (city, stops) can be large enough to be inefficient compared to iterative approaches.

Algorithm Strategy: Graph - Shortest Path (Bellman-Ford / BFS+K)

1. Initialization: Create an array dist of size n filled with infinity, representing the minimum cost to reach each city. Set dist[src] = 0.
2. Iteration Loop: Run a loop k + 1 times. Each iteration represents allowing one additional flight (edge) in the path.
3. State Preservation: Inside the loop, create a copy of the dist array called temp. This is vital. We must calculate distances for the current iteration based only on distances established in the previous iteration. Without this, a single iteration could propagate a path across multiple edges (e.g., A->B->C in one loop), violating the stops constraint.
4. Edge Relaxation: Iterate through the flights list. For every flight (u, v, w):
   • Check if dist[u] (from the previous iteration) is reachable (not infinity).
   • If reachable, minimize the cost: temp[v] = min(temp[v], dist[u] + w).
5. Update State: After checking all flights, replace dist with temp.
6. Result: After k + 1 iterations, dist[dst] contains the cheapest price. If it remains infinity, return -1.

Execution Flow

Let's trace the logic with src=0, dst=2, k=1, and flights 0->1 (100), 1->2 (100), 0->2 (500).

1. Setup:

   • dist = [0, INF, INF]
   • k = 1, so we loop k + 1 = 2 times.

2. Iteration 1 (1 stop max / 1 edge):

   • Create temp = [0, INF, INF] (copy of dist).
   • Process flight 0->1 (cost 100): dist[0] is 0. temp[1] = min(INF, 0 + 100) = 100.
   • Process flight 1->2 (cost 100): dist[1] is INF. Skip.
   • Process flight 0->2 (cost 500): dist[0] is 0. temp[2] = min(INF, 0 + 500) = 500.
   • Update dist = [0, 100, 500].

3. Iteration 2 (2 stops max / 2 edges):

   • Create temp = [0, 100, 500] (copy of dist).
   • Process flight 0->1 (cost 100): temp[1] = min(100, 0 + 100) = 100. No change.
   • Process flight 1->2 (cost 100): dist[1] is 100 (from prev iter). temp[2] = min(500, 100 + 100) = 200.
   • Process flight 0->2 (cost 500): temp[2] = min(200, 0 + 500) = 200. No change.
   • Update dist = [0, 100, 200].

4. Final Result: dist[2] is 200.

Proof of Correctness

The correctness relies on the invariant of the Bellman-Ford algorithm. After the $i$-th iteration of the outer loop, dist[v] stores the shortest path cost from src to v using at most $i$ edges.

Base case: At $i=0$ (before loops), only src is reachable with cost 0 (0 edges). Inductive step: Assume at iteration $i$, dist holds optimal costs for $\le i$ edges. In iteration $i+1$, we consider all edges $(u, v)$ and update $v$'s cost using $u$'s cost from iteration $i$. This effectively extends paths of length $\le i$ by exactly one edge, resulting in paths of length $\le i+1$. Since we terminate after $K+1$ iterations, the resulting dist[dst] reflects the minimum cost using at most $K+1$ edges (which corresponds to $K$ stops).

Pattern Reuse Notes

The Bellman-Ford / BFS+K pattern used here is applicable to other problems involving shortest paths with edge-count constraints or layered graph traversals.

• LeetCode 1129: Shortest Path with Alternating Colors
  • This problem also requires a BFS approach where the state includes the "color" of the last edge, similar to how we track "stops" implicitly by layers.
• LeetCode 743: Network Delay Time
  • While usually solved with Dijkstra, this can be solved with standard Bellman-Ford (relaxing $N-1$ times) to find shortest paths from a source to all nodes.

Reference Implementation

C++ Solution for LeetCode 787

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5using namespace std;
6
7class Solution {
8public:
9    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
10        // Initialize distances to infinity
11        vector<int> dist(n, INT_MAX);
12        dist[src] = 0;
13
14        // Iterate k + 1 times (k stops means k + 1 edges)
15        for (int i = 0; i <= k; ++i) {
16            // Create a temporary array to store updates from this round
17            // This prevents using a path updated in this same iteration
18            vector<int> temp = dist;
19            
20            for (const auto& flight : flights) {
21                int u = flight[0];
22                int v = flight[1];
23                int price = flight[2];
24
25                // If the source node u has been reached previously
26                if (dist[u] != INT_MAX) {
27                    // Relax the edge
28                    if (dist[u] + price < temp[v]) {
29                        temp[v] = dist[u] + price;
30                    }
31                }
32            }
33            // Update the main distance array
34            dist = temp;
35        }
36
37        return dist[dst] == INT_MAX ? -1 : dist[dst];
38    }
39};

Java Solution for LeetCode 787

1import java.util.Arrays;
2
3class Solution {
4    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
5        // Initialize distances with a value larger than any possible path sum
6        int[] dist = new int[n];
7        Arrays.fill(dist, Integer.MAX_VALUE);
8        dist[src] = 0;
9
10        // Iterate k + 1 times
11        for (int i = 0; i <= k; i++) {
12            // Create a copy to prevent using updates from the current iteration
13            int[] temp = Arrays.copyOf(dist, n);
14            
15            for (int[] flight : flights) {
16                int u = flight[0];
17                int v = flight[1];
18                int price = flight[2];
19
20                // Ensure u is reachable before trying to extend the path
21                if (dist[u] != Integer.MAX_VALUE) {
22                    temp[v] = Math.min(temp[v], dist[u] + price);
23                }
24            }
25            // Commit updates for this iteration
26            dist = temp;
27        }
28
29        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
30    }
31}

Python Solution for LeetCode 787

1class Solution:
2    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
3        # Initialize distances with infinity
4        dist = [float('inf')] * n
5        dist[src] = 0
6        
7        # Iterate k + 1 times
8        for _ in range(k + 1):
9            # Create a copy to ensure we only use data from the previous iteration
10            temp = dist[:]
11            
12            for u, v, price in flights:
13                # If the starting node u is reachable
14                if dist[u] != float('inf'):
15                    # Relax the edge
16                    if dist[u] + price < temp[v]:
17                        temp[v] = dist[u] + price
18            
19            # Update the main distance array
20            dist = temp
21            
22        return -1 if dist[dst] == float('inf') else dist[dst]