DAY 42 - Cheapest Flights Within K Stops

Hey everyone! Welcome back to another day of problem-solving. It's day 42, and I can't believe I have been on this for more than 40 days. Never Have I ever committed to upskilling myself so much. Today, we will be doing another graph problem which eventually we will solve using Dijkstra's algorithm. So if you have no clue what we are doing it I suggest reading the previous article on Day 40

Question: Cheapest Flights Within K Stops

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.

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
• Explanation:
• The graph is shown above.
• The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
• Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

• Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
• Output: 200
• Explanation:
• The graph is shown above.
• The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 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
There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst

Intuition: Dijkstra's Algorithm

• The question is pretty easy to understand, so I will not be breaking it down today and heading straight towards the intuition.
• Hmm? We need to find the *path with least cost. It's clear that we need to use a Dijkstra's Algo.
• But we will be using a modified version of it.
• If we go with the classic version of Dijkstra's algo, there might be a case where we don't visit a node because we already have a shorter path but that shorter path might lead to more stops and we need to also maintain atmost K stops.
• So in this problem we will give our priority to stops. We will store distance but it will be our secondary factor.

Algorithm:

Creating the Adjacency List:

• We start by creating the adjacency list representation of the graph.
• We iterate over the flights, which provide information about the flights between different nodes.
• For each flight, we add the destination node and its corresponding weight (price) to the adjacency list of the source node.

Initializing Variables:

• We initialize the necessary variables, including the adjacency list (adj) to store the graph, a distance array (dist) to keep track of the minimum cost to reach each node, and a queue (q) to perform a breadth-first search.
• The distance array is initially set to a large value (1e5) to represent infinity, except for the source node, which is set to 0.

• We enqueue the source node with a cost of 0 and 0 stops, as we start the search from the source node.

  Applying Breadth-First Search:

• While the queue is not empty, we dequeue a pair from the front, which consists of the number of stops, the current node, and the current cost.

• If the number of stops exceeds the given limit (k), we skip further processing for this pair and continue to the next iteration.

• For each adjacent node and its corresponding weight in the adjacency list of the current node, we calculate the new cost by adding the weight to the current cost.

• If the new cost is smaller than the existing cost stored in the distance array for the adjacent node, and the number of stops is within the limit, we update the distance and enqueue the adjacent node with an incremented number of stops and the new cost.

Checking Reachability and Returning the Result:

• After the breadth-first search, if the cost to reach the destination node (dst) remains unchanged (still equal to 1e5), it means that there is no valid path from the source to the destination.
• In this case, we return -1 to indicate that it is not possible to reach the destination.
• Otherwise, we return the cost stored in the distance array for the destination node, as this represents the cheapest price to reach the destination from the source within the given number of stops

Code:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<pair<int,int>> adj[n]; // stores pair of weights and nodes

    // Step 1: Creating the Adjacency List
    for(auto it : flights){
        adj[it[0]].push_back({it[1], it[2]}); // add destination and weight to the adjacency list
    }

    vector<int> dist(n, 1e5); // stores the minimum cost to reach each node
    queue<pair<int,pair<int,int>>> q; // stops, {node and cost} queue

    q.push({0, {src, 0}}); // enqueue the source node with initial cost 0 and 0 stops
    dist[src] = 0; // set the distance of the source node to 0

    // Step 2: Applying Breadth-First Search
    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; // skip processing if the number of stops exceeds the limit

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

            // Update the distance and enqueue the adjacent node if the new cost is smaller
            if(cost + wt < dist[newNode] && stops <= k){
                dist[newNode] = cost + wt;
                q.push({stops + 1, {newNode, cost + wt}});
            }
        }
    }

    // Step 3: Checking Reachability and Returning the Result
    if(dist[dst] == 1e5){
        return -1; // Destination is unreachable
    }

    return dist[dst]; // Return the minimum cost to reach the destination
}

Complexity Analysis:

• Time Complexity: O(N) + O(V+E). Where N is the size cities and V and E are vertices and edges of the graph formed.
• Space Complexity: O(V+E)