Cheapest Flights Within K Stops

How it works

This problem is still about finding the cheapest path with at most k stops.
SPFA (Shortest Path Faster Algorithm) is essentially a queue-optimized Bellman–Ford.

Key observations:

• Each time we relax an edge, we may improve the cost to reach a city.
• However, unlike classic shortest path problems, we must not exceed k stops.
• So every state in the queue must track:
  • the current city
  • the total cost so far
  • the number of stops used
• We only continue expanding a path if stops <= k.

This approach works well because:

• Only promising states (those that improve cost) are pushed into the queue.
• The stop constraint naturally prevents infinite relaxation loops.

Steps

1. Initialize:
   • prices[i] = infinity for all cities.
   • prices[src] = 0.
2. Build an adjacency list from the flight data.
3. Use a queue that stores (currentCost, city, stopsUsed).
   • Start with (0, src, 0).
4. While the queue is not empty:
   • Pop a state (cost, node, stops).
   • If stops > k, skip it.
   • For each outgoing flight (node -> neighbor, price):
     • Compute nextCost = cost + price.
     • If nextCost < prices[neighbor]:
       • Update prices[neighbor].
       • Push (nextCost, neighbor, stops + 1) into the queue.
5. After processing:
   • If prices[dst] is still infinity, return -1.
   • Otherwise, return prices[dst].

Complexity

• Time complexity: O(n * k)
• Space complexity: O(n + m)

Where n is the number of cities, m is the number of flights and k is the number of stops.

Things to watch for

Confusing Stops vs Flights (Off-by-One)

The problem allows at most k stops, which means at most k+1 flights. A common mistake is running Bellman-Ford for k iterations instead of k+1, or checking stops > k when you should check stops == k before taking another flight.

Not Using a Temporary Array in Bellman-Ford

When relaxing edges, using the same array for both reading and writing allows paths from the current iteration to chain together, potentially exceeding the allowed number of flights in a single round.

Using Standard Dijkstra Without Stop Tracking

Standard Dijkstra finds the cheapest path but ignores the stop constraint. A path with fewer stops might be more expensive but still valid, while the cheapest path might exceed k stops. The state must include both cost and number of stops used.

from typing import List
from collections import deque

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [float("inf")] * n
        prices[src] = 0
        adj = [[] for _ in range(n)]
        for u, v, cst in flights:
            adj[u].append([v, cst])

        q = deque([(0, src, 0)])
        while q:
            cst, node, stops = q.popleft()
            if stops > k:
                continue

            for nei, w in adj[node]:
                nextCost = cst + w
                if nextCost < prices[nei]:
                    prices[nei] = nextCost
                    q.append((nextCost, nei, stops + 1))

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

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> prices(n, INT_MAX);
        prices[src] = 0;
        vector<vector<pair<int, int>>> adj(n);
        for (const auto& flight : flights) {
            adj[flight[0]].emplace_back(flight[1], flight[2]);
        }

        queue<tuple<int, int, int>> q;
        q.push({0, src, 0});

        while (!q.empty()) {
            auto [cst, node, stops] = q.front();
            q.pop();
            if (stops > k) continue;

            for (const auto& neighbor : adj[node]) {
                int nei = neighbor.first, w = neighbor.second;
                int nextCost = cst + w;
                if (nextCost < prices[nei]) {
                    prices[nei] = nextCost;
                    q.push({nextCost, nei, stops + 1});
                }
            }
        }
        return prices[dst] == INT_MAX ? -1 : prices[dst];
    }
};