Cheapest Flights Within K Stops

Problem Statement❯

You are given information about n cities connected by m flights. Each flight is represented as [from_i, to_i, price_i] indicating a direct flight from city from_i to city to_i with a cost of price_i.

You are also given three integers:

src – the starting city
dst – the target city
k – the maximum number of allowed stops (i.e., you can take at most k + 1 flights)

Your goal is to find the cheapest price to travel from src to dst with at most k stops. If such a route doesn't exist, return -1.

Examples❯

n	Flights	dst	k	Cheapest Price
4	[[0,1,100],[1,2,100],[2,3,100],[0,3,500]]	3	1	500
4	[[0,1,100],[1,2,100],[2,3,100],[0,3,500]]	3	2	300
3	[[0,1,200],[1,2,200],[0,2,500]]	2	0	500
3	[[0,1,100],[1,2,100]]	2	0	-1

Solution❯

This problem is a variation of the shortest path problem in graphs, where each edge has a cost and we are limited by the number of stops (edges) we can take. We model the cities as nodes and the flights as directed, weighted edges.

To solve this, we use a modified BFS approach using a queue and track cost and stops alongside each city visit. This ensures we can explore paths within the stop limit while trying to find the minimum cost.

We keep a minCost dictionary to record the cheapest cost to reach a city with a given number of stops. Each element in the queue contains:

The current city
The cost to reach that city
The number of stops taken so far

At each step, we dequeue an entry, check if we’ve reached the destination, and if not, push all its neighboring cities into the queue with updated cost and stop count—only if we haven’t exceeded the stop limit.

This approach ensures we explore all viable paths within the allowed stops and return the one with the minimum cost.

Algorithm Steps❯

Build an adjacency list to represent the graph of cities and flights.
Initialize a queue with a tuple (src, 0, 0) representing (current city, cost so far, stops so far).
Maintain a minCost map to record the minimum cost to reach a node with a certain number of stops.
While the queue is not empty:

Dequeue a tuple (city, cost, stops).
If city == dst, update the result if cost is lower.
If stops > k, continue to next iteration.
For each neighbor of the current city, push (neighbor, cost + price, stops + 1) to the queue if this new cost is cheaper than any previously recorded cost to that neighbor with same or fewer stops.

If a path is found, return the cheapest cost; otherwise, return -1.

Code

JavaScript

function findCheapestPrice(n, flights, src, dst, k) {
  const adj = new Map();
  for (const [from, to, price] of flights) {
    if (!adj.has(from)) adj.set(from, []);
    adj.get(from).push([to, price]);
  }

  const queue = [[src, 0, 0]]; // [city, cost, stops]
  const minCost = Array.from({ length: n }, () => Array(k + 2).fill(Infinity));
  minCost[src][0] = 0;

  while (queue.length) {
    const [city, cost, stops] = queue.shift();
    if (stops > k) continue;
    const neighbors = adj.get(city) || [];
    for (const [next, price] of neighbors) {
      const newCost = cost + price;
      if (newCost < minCost[next][stops + 1]) {
        minCost[next][stops + 1] = newCost;
        queue.push([next, newCost, stops + 1]);
      }
    }
  }

  const result = Math.min(...minCost[dst]);
  return result === Infinity ? -1 : result;
}

console.log(findCheapestPrice(4, [[0,1,100],[1,2,100],[2,3,100],[0,3,500]], 0, 3, 1)); // 500
console.log(findCheapestPrice(4, [[0,1,100],[1,2,100],[2,3,100],[0,3,500]], 0, 3, 2)); // 300

⬅ Previous TopicPath With Minimum Effort in Grid using Graphs

Next Topic ⮕Number of Ways to Reach Destination in Shortest Time - Graph Problem