Cheapest Flights Within K Stops

Cheapest Flights Within K Stops

You are given n airports, labeled from 0 to n-1, connected by flights. 

Array “flights” contains details of one-way flights in the form [from_i, to_i, price_i], where “from_i” is the starting airport, “to_i” is the destination airport, and “price_i” is the cost of the flight. 

There are no duplicate flights, and no flights go from an airport to itself.

Cheapest Flights Within K Stops Problem

Examples related to Cheapest Flights Within K Stops Problem

Example 1:

Cheapest Flights Within K Stops Question 1

Example 2:

Cheapest Flights Within K Stops Question 2

Constraints:

  • 1 <= n <= 100
  • fromi != toi
  • 1 <= pricei <= 1000
  • 0 <= src, dst, k < n

Hints to solve Cheapest Flights Within K Stops Problem

Recommended Time & Space Complexity

Aim for a solution with O(n + (m * k)) time and O(n) space, where n is the number of cities, m is the number of flights, and k is the maximum number of stops.

Hint 1:

  • Treat this as a graph problem, where cities are nodes and flights are directed edges with ticket costs as weights.
  • Can you think of a shortest path algorithm that accommodates the k stops condition? More suitable algorithm than Dijkstra’s may help.

Hint 2:

  • Consider using the Bellman-Ford algorithm. Initialize a price array of size n with infinity, setting prices[source] = 0.

  • This array tracks the minimum cost to reach each city. Iterate (k+1) times, updating the cost of each city by extending paths from cities with valid costs.

  • How would you implement this?

Hint 3:

  • At each iteration, update the price array with minimum costs by processing each flight.

  • Use a temporary array to store the updated values.

  • After completing all iterations, return prices[dst]. If it’s still infinity, return -1.

Methods to Solve Cheapest Flights Within K Stops Problem

There are mainly 3 approaches to solve Cheapest Flights Within K Stops problem:

  1. Dijkstra’s Algorithm
  2. Bellman Ford Algorithm
  3. Shortest Path Faster Algorithm

1. Dijkstra’s Algorithm Method

This is a greedy algorithm used to find the shortest path between a source node and all other nodes in a weighted graph.

It works by selecting the node with the smallest tentative distance, then updating the distances of its neighboring nodes, and repeats this until all nodes are visited.

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

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

class Solution {
public:
    int findCheapestPrice(int n, vector>& flights, int src, int dst, int k) {
        int INF = 1e9;
        vector>> adj(n);
        vector> dist(n, vector(k + 5, INF));
        
        for (auto& flight : flights) {
            adj[flight[0]].emplace_back(flight[1], flight[2]);
        }
        
        dist[src][0] = 0;
        priority_queue, 
                       vector>, greater<>> minHeap;
        minHeap.emplace(0, src, -1);
        
        while (!minHeap.empty()) {
            auto [cst, node, stops] = minHeap.top();
            minHeap.pop();
            if (node == dst) return cst;
            if (stops == k || dist[node][stops + 1] < cst) continue;
            for (auto& [nei, w] : adj[node]) {
                int nextCst = cst + w;
                int nextStops = stops + 1;
                if (dist[nei][nextStops + 1] > nextCst) {
                    dist[nei][nextStops + 1] = nextCst;
                    minHeap.emplace(nextCst, nei, nextStops);
                }
            }
        }
        return -1;
    }
};

2. Bellman Ford Algorithm

Dynamic programming approach that calculates the shortest path in a weighted graph, even when negative edge weights exist. It works by iteratively relaxing all edges, updating the shortest distance for each node, and can detect negative weight cycles.

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

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

Code:

class Solution {
public:
    int findCheapestPrice(int n, vector>& flights, int src, int dst, int k) {
        vector prices(n, INT_MAX);
        prices[src] = 0;

        for (int i = 0; i <= k; i++) {
            vector tmpPrices = prices;

            for (const auto& flight : flights) {
                int s = flight[0];
                int d = flight[1];
                int p = flight[2];

                if (prices[s] == INT_MAX)
                    continue;

                if (prices[s] + p < tmpPrices[d])
                    tmpPrices[d] = prices[s] + p;
            }

            prices = tmpPrices;
        }

        return prices[dst] == INT_MAX ? -1 : prices[dst];
    }
};

3. Shortest Path Faster Algorithm

This is an optimized version of the Bellman-Ford algorithm, where nodes are processed in order of the shortest known distance. It uses a priority queue to speed up the relaxation process, offering better performance for many graphs.

  • 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.

Code:

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

        queue> 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];
    }
};

More Articles