🌱 Keegan's Digital Garden

787. Cheapest Flights Within K Stops

2 min read

📝 Problem Details

input integer n representing the number of cities connected by some number of flights input array flights ⇒ flights[i] = [from, to, price] input integers: src dst k return the cheapest price from src to dst with at MOST k stops return -1 if not possible

💭What Were My Initial Thoughts?

- we are looking for the shortest path from src to destination with the added constraint that this shortest path in weight cannot exceed k nodes visited
- an extension of dijkstra's shortest path algorithm seems appropriate
- instead of using dijkstra's we can use bellman ford as it works well when we need to limit the number of edges to relax

💡 Explanation of Solution

Instead of a priority queue, Bellman-Ford relaxes edges k+1 times.

Algorithm:

  1. Initialize an array dist[] with INF, except dist[src] = 0.
  2. Iterate k+1 times:
    • Create a temporary array temp[] (copy of dist[]).
    • Relax all flights:
      temp[to] = min(temp[to], dist[from] + price)
    • Swap dist[] with temp[] after each iteration.
  3. Return dist[dst], or -1 if unreachable.

⌛ Complexity Analysis

Time Complexity: O(k * E)
Space Complexity: O(k * E)

💻 Implementation of Solution

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> dist (n, INT_MAX);
        dist[src] = 0;
 
        for(int i = 0; i <= k; i++) {
            vector<int> temp = dist; // create a copy for this iteration
 
            for(const auto& flight : flights) {
                int from = flight[0];
                int to = flight[1];
                int weight = flight[2];
                if(dist[from] != INT_MAX) {
                    temp[to] = min(temp[to], dist[from] + weight);
                }
            }
            dist = temp;
        }
 
        return dist[dst] == INT_MAX ? -1 : dist[dst];
    }
};

Graph View