Cheapest Flights Within K Stops

LeetCode Problem #787

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.

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.

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

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

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

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

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

Image Sources:

https://www.programiz.com/dsa/graph

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.

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. 

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: <source city, <destination city, <price>>

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.

Time Complexity: O(n^2logn)

Code

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    // mapping -> <source city, <destination city, price>>
    vector<vector<pair<int, int>>> price_map(n);
    for(vector<int>& f : flights) {
        price_map[f[0]].push_back({f[1], f[2]});
    }
    // priority queue -> <current total price , <current source city, maximum allowed distance to destination>>
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> 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<int> 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<int, int>& 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;
}