Cheapest Flights Within K Stops

Problem

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.

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 graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

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 marked in red and has 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 no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

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

Solution

Approach 1: Modified Dijkstra with Priority Queue

The key insight is to modify Dijkstra’s algorithm to track both cost and number of stops, allowing suboptimal costs if they have fewer stops.

Implementation

import heapq
from collections import defaultdict

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # Build graph
        graph = defaultdict(list)
        for u, v, price in flights:
            graph[u].append((v, price))

        # Min heap: (cost, city, stops)
        min_heap = [(0, src, 0)]

        # Track best cost to reach each city with given stops
        best = {}

        while min_heap:
            cost, city, stops = heapq.heappop(min_heap)

            if city == dst:
                return cost

            if stops > k:
                continue

            if (city, stops) in best and best[(city, stops)] < cost:
                continue

            best[(city, stops)] = cost

            # Explore neighbors
            for next_city, price in graph[city]:
                new_cost = cost + price
                heapq.heappush(min_heap, (new_cost, next_city, stops + 1))

        return -1

Approach 2: Bellman-Ford (Dynamic Programming)

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # Initialize distances
        prices = [float('inf')] * n
        prices[src] = 0

        # Relax edges k+1 times (k stops means k+1 edges)
        for i in range(k + 1):
            temp = prices.copy()

            for u, v, price in flights:
                if prices[u] != float('inf'):
                    temp[v] = min(temp[v], prices[u] + price)

            prices = temp

        return prices[dst] if prices[dst] != float('inf') else -1

Approach 3: BFS with Level Tracking

from collections import deque, defaultdict

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # Build graph
        graph = defaultdict(list)
        for u, v, price in flights:
            graph[u].append((v, price))

        # BFS: (city, cost)
        queue = deque([(src, 0)])
        min_cost = float('inf')

        # Track best cost to each city
        best_cost = [float('inf')] * n
        stops = 0

        while queue and stops <= k:
            size = len(queue)

            for _ in range(size):
                city, cost = queue.popleft()

                for next_city, price in graph[city]:
                    new_cost = cost + price

                    # Only explore if better cost found
                    if new_cost < best_cost[next_city]:
                        best_cost[next_city] = new_cost
                        queue.append((next_city, new_cost))

                        if next_city == dst:
                            min_cost = min(min_cost, new_cost)

            stops += 1

        return min_cost if min_cost != float('inf') else -1

Complexity Analysis

Dijkstra Approach:

Time Complexity: O(E * K * log(N * K)), where E is edges, N is cities, K is stops.
Space Complexity: O(N * K) for tracking best costs at different stop counts.

Bellman-Ford Approach:

Time Complexity: O(K * E), where E is number of flights.
Space Complexity: O(N) for distance arrays.

BFS Approach:

Time Complexity: O(K * E) in worst case.
Space Complexity: O(N) for the queue and cost tracking.

Key Insights

Constrained Shortest Path: Unlike standard shortest path, we have a constraint on number of stops (edges).
Suboptimal Paths Matter: A more expensive path with fewer stops might be valid when a cheaper path exceeds k stops.
Modified Dijkstra: Track both cost and stops; accept a path even if cost isn’t minimal if stops are fewer.
Bellman-Ford DP: Iteratively relax edges k+1 times, where each iteration allows one more edge in the path.
Level-Order BFS: Process cities level by level (stops), tracking best cost to reach each city at each level.
Early Termination: In Dijkstra approach, return immediately when destination is popped from heap with valid stops.