Cheapest Flights Within K Stops

In this page, we will solve the Cheapest Flights Within K Stops problem using two different approaches: Breadth First Search and Depth First Search technique. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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.

Examples

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

Example 2:

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

Constraints

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

---

Solution for Cheapest Flights Within K Stops Problem

Intuition and Approach

To solve the problem of finding the minimum cost to reach a destination from a source with a restriction on the number of stops, we can use Dijkstra’s Algorithm with a key modification. Instead of prioritizing minimum distance, we prioritize the minimum number of stops in the priority queue. This ensures that we explore paths with fewer stops, which helps us avoid premature termination of the algorithm due to exceeding the stop limit.

However, since the number of stops increases monotonically (by 1 each iteration), we don't actually need a priority queue. A simple queue is sufficient because we always pop the element with the lesser number of stops first, thus eliminating the extra log(N) complexity associated with insertion and deletion in a priority queue. This change improves the algorithm's efficiency.

• Breadth First Search
• Depth First Search

Approach 1: Breadth First Search

To solve the problem, create an adjacency list and initialize a queue to store pairs. Set up a distance array with large values to mark unvisited nodes and set the source node's distance to 0. Push the source node into the queue with distance 0 and 0 stops. Process the queue by popping elements, and for each adjacent node, update the distance and push it back into the queue if the current distance is less and the stop count is below K. Continue until the queue is empty. If the destination is reached within the required stops, return the distance; otherwise, return -1 if no valid path exists.

Codes in Different Languages

JavaScript

Written by @aryan-1309

 var findCheapestPrice = function(n, flights, src, dst, K) {
     let graph = {} // {from: { to: price }, {to: price}}
     
     for (let [source, destination, price] of flights){
         if (!graph.hasOwnProperty(source)) {
             graph[source] = {}
         }
         graph[source][destination] = price
     }

     let queue = [[0,src,0]]
     
     while (queue.length ) {     
         let [price, city, connections] = queue.shift()
         if (city == dst) return price
         if (connections > K) continue
         
         if (graph[city]) {
             for (let nextStops in graph[city]) {
                 let cost = graph[city][nextStops]
                 queue.push([cost + price, nextStops, connections + 1])
             }
         }
         queue.sort((a,b) => a[0]-b[0])
         
     }
     return -1
 }

TypeScript

Written by @aryan-1309

 function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
     const adj = new Map();
     const visited = new Array(n).fill(Number.MAX_VALUE);
     visited[src] = 0;
 
     for (const [from, to, price] of flights) {
         if (!adj.has(from)) {
             adj.set(from, []);
         }
         adj.get(from).push([to, price]);
     }
 
     const queue = [[src, 0]];
     k++;

     while (k-- > 0 && queue.length > 0) {
         const size = queue.length;
         for (let i = 0; i < size; i++) {
             const [currNode, currPrice] = queue.shift();
             if (adj.has(currNode)) {
                 for (const [nextNode, nextPrice] of adj.get(currNode)) {
                     const newPrice = currPrice + nextPrice;
                     if (newPrice < visited[nextNode]) {
                         visited[nextNode] = newPrice;
                         queue.push([nextNode, newPrice]);
                     }
                 }
             }
         }
     }
 
     return visited[dst] === Number.MAX_VALUE ? -1 : visited[dst];
 };

Python

Written by @aryan-1309

 class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
 graph = [[] for _ in range(n)]
 minHeap = [(0, src, k + 1)]  # (d, u, stops)
 dist = [[math.inf] * (k + 2) for _ in range(n)]

 for u, v, w in flights:
   graph[u].append((v, w))

 while minHeap:
   d, u, stops = heapq.heappop(minHeap)
   if u == dst:
     return d
   if stops > 0:
     for v, w in graph[u]:
       newDist = d + w
       if newDist < dist[v][stops - 1]:
         dist[v][stops - 1] = newDist
         heapq.heappush(minHeap, (newDist, v, stops - 1))

 return -1

Java

Written by @aryan-1309

 class Solution {
     public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
         List<Pair<Integer, Integer>>[] graph = new List[n];
         // (d, u, stops)
         Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
         int[][] dist = new int[n][k + 2];
         Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));

         for (int i = 0; i < n; ++i)
         graph[i] = new ArrayList<>();

         for (int[] f : flights) {
         final int u = f[0];
         final int v = f[1];
         final int w = f[2];
         graph[u].add(new Pair<>(v, w));
         }

         minHeap.offer(new int[] {0, src, k + 1}); // Start with node src with d == 0
         dist[src][k + 1] = 0;

         while (!minHeap.isEmpty()) {
         final int d = minHeap.peek()[0];
         final int u = minHeap.peek()[1];
         final int stops = minHeap.poll()[2];
         if (u == dst)
             return d;
         if (stops > 0)
             for (Pair<Integer, Integer> pair : graph[u]) {
             final int v = pair.getKey();
             final int w = pair.getValue();
             final int newDist = d + w;
             if (newDist < dist[v][stops - 1]) {
                 dist[v][stops - 1] = newDist;
                 minHeap.offer(new int[] {d + w, v, stops - 1});
             }
             }
         }

         return -1;
     }
 }

C++

Written by @aryan-1309

 class Solution {
 public:
     int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
         
         //{to,price}
         vector<pair<int,int>> adj[n];

         for(auto x : flights){
             
             int from = x[0];
             int to = x[1];
             int price = x[2];

             adj[from].push_back({to,price});
         }

         vector<int> dist(n,1e9);
         dist[src] = 0;
         
         // {stops,{node,dist}}
         queue<pair<int,pair<int,int>>> q;
         q.push({0,{src,0}});
         
         while(!q.empty()){

         auto it = q.front();
         q.pop();

         int stops = it.first;
         int node = it.second.first;
         int cost = it.second.second;

         if(stops>k) continue;

         for(auto itr : adj[node]){
             int adjNode = itr.first;
             int edgw = itr.second;

             if(cost+edgw < dist[adjNode] && stops<=k){
                 dist[adjNode] = cost + edgw;
                 q.push({stops+1,{adjNode,cost+edgw}});
             }
         }

         }

         if(dist[dst]==1e9) return -1;
         return dist[dst];
     }
 };

Complexity Analysis

• Time Complexity: $O(N)$
• Space Complexity: $O(|E|+|V|)$
• Where N is the Number of flights / Number of edges..
• Where E = Number of edges (flights.size()) and V = Number of Airports.

References

• LeetCode Problem: LeetCode Problem
• Solution Link: Cheapest Flights Within K Stops Solution on LeetCode