Problem Statement

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Additional information

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 10^4
• There will not be any multiple flights between two cities.
• 0 <= src, dst, k < n
• src != dst

Example 1:

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

Output: 700

Explanation: The optimal path with at most 1 stop from city 0 to 3 is 0 -> 1 -> 3 with cost 100 + 600 = 700.
Note that the path 0 -> 1 -> 2 -> 3 costs 400, but it requires 2 stops which is greater than 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: The optimal path with at most 1 stop from city 0 to 2 is 0 -> 1 -> 2 with cost 100 + 100 = 200.

Example 3:

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

Output: 500

Explanation: The optimal path with at most 0 stops (direct flight) from city 0 to 2 is 0 -> 2 with cost 500.

Breadth-First Search (BFS with Pruning)

Intuition

A highly intuitive way to explore paths with a strict limit on the number of stops is using Breadth-First Search (BFS). BFS naturally processes graphs layer by layer.

We can start at the src city and push it into a queue. Every time we process a layer, we are simulating a "stop". We repeat this layer-by-layer expansion up to k + 1 times (since k stops equals k + 1 flights/edges).

To prevent our queue from exploding exponentially and hitting a Time Limit Exceeded (TLE) error, we must prune inefficient paths. We maintain an array min_cost tracking the cheapest way to reach each city. We only add a neighboring city to our queue if the current path's price is strictly cheaper than the recorded min_cost for that city.

Algorithm

1. Build an adjacency list adj mapping each departure city to a list of tuples (destination, price).
2. Initialize a min_cost array of size n with infinity (float("inf")). Set min_cost[src] = 0.
3. Initialize a deque (queue) holding a tuple of (current_city, current_cost).
4. Track the number of stops starting at 0.
5. While the queue is not empty and stops <= k:

• Get the level_size of the queue to process exactly one layer.

• Loop level_size times:

• Pop curr_city and curr_cost.

• Iterate through the neighbors of curr_city in adj.

• If curr_cost + flight_price < min_cost[neighbor]:

• Update min_cost[neighbor] = curr_cost + flight_price.

• Append (neighbor, curr_cost + flight_price) to the queue.

• Increment stops by 1.

6. Return min_cost[dst] if it is not infinity, otherwise return -1.

def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    adj = defaultdict(list)
    for u, v, w in flights:
        adj[u].append((v, w))
        
    q = deque([(src, 0)])
    min_cost = [float("inf")] * n
    min_cost[src] = 0
    
    stops = 0
    
    # Process level by level up to k stops (which is k + 1 edges)
    while q and stops <= k:
        level_size = len(q)
        
        for _ in range(level_size):
            curr_city, curr_cost = q.popleft()
            
            for neighbor, price in adj[curr_city]:
                if curr_cost + price < min_cost[neighbor]:
                    min_cost[neighbor] = curr_cost + price
                    q.append((neighbor, curr_cost + price))
                    
        stops += 1
        
    return min_cost[dst] if min_cost[dst] != float("inf") else -1

Time & Space Complexity

• Time complexity: O(V + E * K)

• Reason: In the worst-case scenario, we explore all Edges (E) at every level of the BFS. Since we go at most K + 1 levels deep, the upper bound is strictly proportional to E * K. Building the adjacency list takes O(E).

• Space complexity: O(V + E)

• Reason: The adjacency list takes O(V + E) space. The queue and the min_cost array take up to O(V) space.

Bellman-Ford Algorithm - Optimal

Intuition

The requirement "cheapest path with at most K stops" perfectly aligns with the mechanics of the Bellman-Ford Algorithm.

Standard Bellman-Ford finds the shortest path by relaxing all edges V - 1 times. In this problem, we simply restrict it to relaxing the edges exactly k + 1 times! This perfectly simulates finding the shortest path using at most k + 1 edges (which mathematically translates to k intermediate stops).

To prevent multiple sequential flights from being processed in a single iteration (which would violate the stop limit), we must use a temporary copy of our prices array (temp_prices). We read the starting costs from the old array, but save the newly discovered cheaper costs to the temporary array.

Algorithm

1. Initialize a prices array of size n with infinity (float("inf")).
2. Set the starting city's price to 0: prices[src] = 0.
3. Loop exactly k + 1 times:

• Create a copy of the current prices: temp_prices = prices.copy().

• Iterate through every flight u, v, w in flights.

• If prices[u] is not infinity and prices[u] + w < temp_prices[v]:

• Update temp_prices[v] = prices[u] + w.

• Overwrite the main array for the next level: prices = temp_prices.

4. Return prices[dst] if it is not infinity, else -1.

def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    prices = [float("inf")] * n
    prices[src] = 0
    
    # Relax the edges exactly k + 1 times
    for i in range(k + 1):
        temp_prices = prices.copy()
        
        for u, v, w in flights:
            # If the source city is reachable, and this flight is cheaper
            if prices[u] != float("inf") and prices[u] + w < temp_prices[v]:
                temp_prices[v] = prices[u] + w
                
        prices = temp_prices
        
    return prices[dst] if prices[dst] != float("inf") else -1

Time & Space Complexity

• Time complexity: O(K * E)

• Reason: We iterate over every single flight edge (E) exactly K + 1 times. This is highly efficient and eliminates the need to build and traverse an adjacency list.

• Space complexity: O(V)

• Reason: We completely bypass the adjacency list. The only memory overhead is the prices and temp_prices arrays, which both take exactly O(V) space.