Problem Description

You are given n cities numbered from 0 to n-1 and a list of flights, where each flight is represented as [from, to, price]. Your task is to find the cheapest price from a given source city src to a destination city dst with at most K stops (where a stop is a transfer at an intermediate city). If there is no such route, return -1.

• Each flight can be used at most once.
• You may visit a city more than once, as long as the total number of stops does not exceed K.
• The input guarantees at least one solution may exist, but it is possible that no valid route is available.
• Constraints:
  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1))
  • flights[i] = [fromi, toi, pricei]
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 10^4
  • 0 <= src, dst, K < n

Thought Process

At first glance, this problem looks like a variation of the shortest path problem in a weighted directed graph, but with the extra constraint of a maximum number of stops (K). A brute-force approach would be to try all possible paths from src to dst with at most K stops and pick the one with the lowest cost. However, this quickly becomes infeasible as the number of cities and flights grows.

To optimize, we need a way to systematically explore possible routes while keeping track of both the cost and the number of stops. Traditional shortest path algorithms like Dijkstra’s do not work directly because they do not account for the "number of stops" constraint. Instead, a modified Breadth-First Search (BFS) or a priority queue-based approach (similar to Dijkstra’s but with an extra state for stops) can be used. This allows us to explore all possible paths up to K stops efficiently and find the minimum cost.

Solution Approach

We can solve this problem using a variation of Dijkstra's algorithm with a priority queue (min-heap), where each state in the queue keeps track of:

• The current city
• The total cost to reach this city
• The number of stops taken so far

1. Build the Graph:
   • Use an adjacency list to represent the flights between cities and their costs for fast lookup.
2. Initialize the Priority Queue:
   • Start with the source city, cost 0, and 0 stops.
   • The queue orders states by their current total cost (min-heap).
3. BFS/Dijkstra with Stop Constraint:
   • While the queue is not empty, pop the city with the lowest current cost.
   • If the city is the destination, return the cost (since it’s the cheapest found so far with ≤ K stops).
   • If the number of stops exceeds K, skip this state.
   • For each neighbor, push a new state to the queue with updated cost and stops.
4. Visited States Optimization:
   • Optionally, keep track of the minimum number of stops used to reach each city to avoid unnecessary work.
5. Return -1 if No Route:
   • If the queue is exhausted without reaching the destination within the stop limit, return -1.

Example Walkthrough

Example:
n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500]], src = 0, dst = 3, K = 1

• Step 1: Build the graph:
  • 0 → 1 (100), 0 → 2 (500)
  • 1 → 2 (100)
  • 2 → 3 (100)
• Step 2: Start BFS with (city=0, cost=0, stops=0).
• Step 3: From city 0, we can go to:
  • city 1: cost=100, stops=1
  • city 2: cost=500, stops=1
  Both are pushed to the queue.
• Step 4: Pop (city 1, cost 100, stops 1):
  • From city 1, go to city 2: cost=200, stops=2 (exceeds K=1, so skip)
• Step 5: Pop (city 2, cost 500, stops 1):
  • From city 2, go to city 3: cost=600, stops=2 (exceeds K=1, so skip)
• Step 6: No more nodes in the queue. No valid route found within 1 stop.
• Result: Return -1.

If K = 2, the path 0 → 1 → 2 → 3 is possible with cost 300 and 2 stops.

Time and Space Complexity

Brute-force Approach:
Tries all possible paths from src to dst with at most K stops. In the worst case, this is exponential: O(n^{K+1}) time, which is infeasible for large n or K.

Optimized Priority Queue Approach:

• Time Complexity: O(E * K) where E is the number of flights. Each node can be processed up to K times (once for each possible number of stops).
• Space Complexity: O(n * K) for the queue and visited states.

Summary

The key to solving "Cheapest Flights Within K Stops" is recognizing it as a constrained shortest path problem. By using a priority queue and tracking both cost and number of stops, we efficiently explore all viable routes without exceeding the stop limit. The solution is elegant because it combines the strengths of BFS and Dijkstra’s algorithm, ensuring optimality while respecting the problem’s unique constraints.

Code Implementation

import heapq
from collections import defaultdict

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K):
        graph = defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))
        heap = [(0, src, 0)]  # (cost, city, stops)
        visited = dict()  # (city, stops): cost

        while heap:
            cost, city, stops = heapq.heappop(heap)
            if city == dst:
                return cost
            if stops > K:
                continue
            for nei, price in graph[city]:
                if (nei, stops) not in visited or cost + price < visited[(nei, stops)]:
                    visited[(nei, stops)] = cost + price
                    heapq.heappush(heap, (cost + price, nei, stops + 1))
        return -1
      

#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<pair<int, int>>> graph(n);
        for (auto& f : flights)
            graph[f[0]].emplace_back(f[1], f[2]);
        // min-heap: (cost, city, stops)
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        pq.emplace(0, src, 0);
        unordered_map<int, int> visited; // key: city * (K+2) + stops

        while (!pq.empty()) {
            auto [cost, city, stops] = pq.top(); pq.pop();
            if (city == dst) return cost;
            if (stops > K) continue;
            for (auto& [nei, price] : graph[city]) {
                int key = nei * (K+2) + stops;
                if (!visited.count(key) || cost + price < visited[key]) {
                    visited[key] = cost + price;
                    pq.emplace(cost + price, nei, stops + 1);
                }
            }
        }
        return -1;
    }
};
      

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] f : flights) {
            graph.computeIfAbsent(f[0], x -> new ArrayList<>()).add(new int[]{f[1], f[2]});
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, src, 0}); // {cost, city, stops}
        Map<String, Integer> visited = new HashMap<>();

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0], city = curr[1], stops = curr[2];
            if (city == dst) return cost;
            if (stops > K) continue;
            if (!graph.containsKey(city)) continue;
            for (int[] nei : graph.get(city)) {
                String key = nei[0] + "," + stops;
                if (!visited.containsKey(key) || cost + nei[1] < visited.get(key)) {
                    visited.put(key, cost + nei[1]);
                    pq.offer(new int[]{cost + nei[1], nei[0], stops + 1});
                }
            }
        }
        return -1;
    }
}
      

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} K
 * @return {number}
 */
var findCheapestPrice = function(n, flights, src, dst, K) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v, w] of flights) {
        graph[u].push([v, w]);
    }
    const heap = [[0, src, 0]]; // [cost, city, stops]
    const visited = new Map();

    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]);
        const [cost, city, stops] = heap.shift();
        if (city === dst) return cost;
        if (stops > K) continue;
        for (const [nei, price] of graph[city]) {
            const key = nei + ',' + stops;
            if (!visited.has(key) || cost + price < visited.get(key)) {
                visited.set(key, cost + price);
                heap.push([cost + price, nei, stops + 1]);
            }
        }
    }
    return -1;
};