# Cheapest Flights Within K Stops ## Problem Statement There are `n` cities connected by `m` flights. Each flight starts from city `u` and arrives at `v` with a price `w`. Now given all the cities and flights, together with starting city `src` and the destination `dst`, your task is to find the cheapest price from `src` to `dst` with up to `k` stops. If there is no such route, output `-1`. {% hint style="info" %} Constraints: * The number of nodes `n` will be in the range `[1, 100]`, with nodes labelled from `0` to `n - 1`. * The size of `flights` will be in the range `[0, n * (n - 1) / 2]`. * The format of each flight will be `(src, dst, price)`. * The price of each flight will be in the range `[1, 10000]`. * `k` is in the range of `[0, n - 1]`. * There will not be any duplicated flights or self cycles. {% endhint %} ## Testcases ``` Example 1: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 Output: 200 Explanation: The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture. ``` ![Example 1 Graph](/files/-M9qOdEyFhUyg_49xF_p) ``` Example 2: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 Output: 500 Explanation: The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture. ``` ![Example 2 Graph](/files/-M9qPEcPnYK0fCvBOnGT) ## Problem Explanation There are several possible paths that can be taken to reach a particular destination city from a source city. In this problem, there are intermediate cities through which one can travel in order to reach their destination. However, the problem stipulates that we cannot travel through more than a given number of intermediate cities. The problem asks us to find the lowest price that we have to pay to reach the destination from the source, given that we can stop at a maximum of `k` stops. Including the destination city, this means that `k + 1` nodes may be traversed in the flight path. ## Prerequisite Knowledge ### Priority Queue A priority queue is a special type of queue wherein, every element is associated with a priority value and is processed according to the magnitude of this value. While the conventional queue data structure follows a **first-in-first-out (FIFO)** but in the case of a priority queue, the values are dequeued on the basis of their **priority value**. In the example below, a higher number indicates a higher priority, but the priority parameters can be designed according to our needs. ![Priority Queue](/files/-M9qp1o-yKbjxfLiUKr0) ### Graph Data Structure A graph is a non-linear data structure which comprises a finite number of nodes (vertices) and a set of edges which connect a pair of nodes. Every edge in a graph is represented as an ordered pair of vertices. In the example below, the nodes or vertices are represented as, `0, 1, 2, 3` The edges connecting these nodes are represented as, `{0, 1}, {0, 2}, {0, 3}, {1, 2}` Two nodes are said to have **adjacency** if they have an edge which connects them. In order to traverse from a source node to a destination node through other nodes, we follow a sequence of edges called a **path**. ![Graph](/files/-M9rgUeUosXnWgNyQfbR) #### Adjacency Matrix A common way to represent a graph is through an adjacency matrix. The relationship between each node and the other nodes in the graph is represented using a two-dimensional matrix with the number of rows and columns equal to the number of nodes in the graph. If an edge exists between two nodes, `i` and `j`, cell `a[i, j]` will be filled with the value 1. If there is no edge connection between the two nodes, the respective cell is filled with the value 0. ![Adjacency Matrix](/files/-M9rfzVkD0XARFWN1Iil) **Image Sources**: ### Dijkstra's Algorithm Dijkstra's Algorithm is used to find the shortest path between any two nodes of a graph. The algorithm accomplishes this by building a set of nodes that have a minimum distance from the source. This algorithm can be applied to weighted graphs. A weighted graph is simply a graph where the edges which connect some nodes have a non-negative value or *cost* associated with it. In this problem, the *price of the flight* is considered as the weight. {% code title="Algorithm" %} ``` Initialize the first node with distance 0 and the remaining nodes with distance ∞. The distance of the starting node is marked as permanent and the remaining distances are marked as temporary and will be changed. Set the starting node as active. Set the temporary distances of all neighboring nodes of the active nodes by calculating the cumulative distance along with the weights of the edges. Update the distance if the calculated distance of a node is smaller than the current distance. Set the node with the minimal temporary distance as the active node and make its distance value as permanent. Repeat steps 4 to 7 until the destination has been reached. ``` {% endcode %} ## Algorithm ### Dijkstra's Algorithm Approach This approach is based on Dijkstra's Algorithm, with the primary difference being that a global optimum value is not maintained. The global optimum is not needed in this case because the distance is not the only parameter which must be concerned, and by extension, evaluated for optimization. There could be routes wherein, the distance is shorter, but go through more stops. If this is not allowed according to the constraints, it cannot be considered as the optimal route. A priority queue is used to store all possible routes with `0 to K` stops such that they can all be processed. 1. Initialize a mapping which stores the flight information as: `>` 2. Initialize a min priority queue with each object being an integer array holding values: a. Current total price b. Current source city c. Maximum allowed hops to destination The priority queue compares each object with the total price so far. 3. Add the original source city to the priority queue and set the price to 0 and the number of hops allowed to `k + 1`. 4. While there are cities remaining to be traversed, a. Identify and remove the minimum object from the priority queue. b. Get the current total price, the current source city, and the number of hops to the destination allowed from the minimum object. 5. Check if the current source is equal to the destination and the number of stops made is less than `k`. a. If the destination has been reached and the conditions are satisfied, return the distance value. b. If the destination has not been reached, find all the connected flights that fly from the current source. Calculate the new price, identify the current source, find the new distance, and add these values to the priority queue. 6. If there are no cities remaining to be traversed or no flights that satisfy the conditions, return -1. {% hint style="info" %} Time Complexity: O(n^2logn) {% endhint %} ## Code ```cpp int findCheapestPrice(int n, vector>& flights, int src, int dst, int K) { // mapping -> > vector>> price_map(n); for(vector& f : flights) { price_map[f[0]].push_back({f[1], f[2]}); } // priority queue -> > priority_queue, vector>, greater>> pq; // Add source city to the priority queue with price 0, and allowed distance as k + 1 // Number of stops = k -> Number of nodes = k + 1 (including destination) pq.push({0, src, K + 1}); while(!pq.empty()) { // Remove min object from the priority queue vector top = pq.top(); pq.pop(); // Get current total price (distance), current source city, and distance to destination allowed from min object int price = top[0]; int current_src = top[1]; int hops_allowed = top[2]; // If the current source is the destination, and the number of hops is less than k, return the distance if(dst == current_src) { return price; } // If the destination has not been reached, check if more hops are allowed if(hops_allowed > 0) { // Find all the connected flights that fly from the current source for(pair& v : price_map[current_src]) // Calculate the new price, new source, and new hops allowed and push it into the priority queue pq.push({price + v.second, v.first, hops_allowed - 1}); } } // If no cities are left and there are no routes that satisfy the conditions, return -1 return -1; } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-2/cheapest-flights-within-k-stops.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.